5.9. Грамматический анализ и автоматы

В предыдущем параграфе рассматривались формальные грамматики и порождение с их помощью, начиная с начального символа, языков или отдельных последовательностей, принадлежащих языкам. В этом параграфе решим обратную задачу. Дана грамматика и некоторая последовательность. Требуется определить, принадлежит ли данная последовательность языку, порождаемому данной грамматикой, или нет. Грамматика в этом случае выступает как средство распознавания последовательностей языка. Ограничимся случаем самой простой грамматики — автоматной. Для распознавания последовательностей, порождаемых автоматными грамматиками, может быть использована модель конечного автомата, рассмотренная в настоящей главе, поскольку между автоматной грамматикой и конечным автоматом имеется тесная связь. Суть этой связи состоит в том, что для любого языка, все последовательности которого порождаются некоторой автоматной грамматикой, может

быть всегда построен конечный автомат (не обязательно детерминированный), реализующий все эти последовательности, и этот автомат может быть использован для распознавания последовательностей данного языка.

В модели конечного автомата, необходимого для распознавания последовательностей языка и называемого распознающим, удобно выделить из множества всех внутренних состояний подмножество с В, состояния которого называются финальными, и не использовать множество выходных состояний и функцию выхода. Распознающий автомат определяется следующим образом:

где — входной алфавит; — внутренний алфавит (множество состояний автомата); функция переходов, записываемая так же, как — непустое множество финальных состояний, Количество финальных состояний выбирается из практических соображений. Мы ограничимся одним финальным состоянием

Начальное состояние

Будем полагать, что Последовательности а. языка, порождаемого какой-либо автоматной грамматикой, поступают на вход распознающего автомата. Если последовательность принадлежит языку, то автомат после подачи последнего символа а. последовательности а. должен оказаться в одном из состояний множества финальных состояний. Если последовательность не принадлежит языку, то этого не произойдет, и этот факт используется для распознавания последовательностей, не принадлежащих языку.

Распознающий автомат построим по распознающей грамматике следующим образом.

Каждому нетерминальному символу грамматики сопоставим внутреннее состояние

Каждому правилу сопоставим дугу (переход) из состояния в состояние по входному состоянию а.

Каждому правилу а сопоставим дугу (переход) из состояния в состояние по входному состоянию а.

Пример. Дана автоматная грамматика С:

Порождаемый язык

Конечный автомат, распознающий язык

Этот простой конечный автомат не является детерминированным. Можно показать, что любой недетерминированный конечный автомат может быть преобразован в эквивалентный детерминированный автомат или в систему эквивалентных детерминированных автоматов. Под эквивалентностью автоматов в данном случае понимается их способность распознавать одни и те же языки. Системы автоматов способны распознавать и более мощные языки, например, порождаемые контекстно-свободными грамматиками. Таким образом, модель конечного автомата может служить основой для распознавания достаточно широкого класса языков. Учитывая это, модель конечного автомата может быть использована для создания агентов, способных выполнять следующие функции.

Распознавать языки (последовательности, предложения, сообщения в этих языках), на которых описаны знания о среде, проверяя, таким образом, синтаксическую правильность представления знаний о среде.

Конечный автомат, распознающий язык, на котором представлены знания о среде, может рассматриваться как некий эквивалент этой среды. В этом

Рис. 5.18. Граф переходов распознающего автомата

случае состояния автомата соответствуют состояниям среды, и автомат может быть использован агентом для поиска целевых состояний в пространстве состояний, как это было уже продемонстрировано ранее в настоящей главе.

В том и другом случае (распознавании и поиске цели), находя те или иные состояния, агент может совершать определенные действия или выдавать сообщения другим агентам. Например, в случае распознавания действия могут быть направлены на перевод одних сообщений (последовательностей языка) в другие. Рассмотрим на простейшем примере, как это может бьггь сделано.