Пред.Страница
След.Страница
Раздел Содержание
2. Автоматные грамматики и распознаватели
Формальные грамматики можно рассматривать как инструмент, позволяющий строить цепочки языка согласно правилам, которые зафиксированы в схеме грамматики. Другими словами, если задана грамматика, определяющая язык, то всегда можно построить любую цепочку этого языка. Для практических применений большое значение имеет другая задача, которую называют задачей распознавания. Она формулируется следующим образом. Задана цепочка, состоящая из терминальных символов, и формальная грамматика, требуется определить, принадлежит ли заданная цепочка языку, порождаемому заданной грамматикой.
В общем случае эта задача может быть решена при помощи непосредственного использования правил грамматики. Нужно находить в заданной цепочке фрагменты, совпадающие с правыми частями правил грамматики, и заменять эти части символами левых частей правил. Операцию замены части заданной цепочки, совпадающей с правой частью какого – либо правила, левой частью этого правила называют непосредственным сворачиванием. Если после выполнения последовательности непосредственных сворачиваний удается получить начальный символ грамматики, то заданная цепочка принадлежит языку, порождаемому грамматикой.
Допустим, что задана грамматика, схема которой имеет вид:
R =
{<I>→ a <B> x, B → b <B>, <B> → y},
и цепочка символов abyx. Выполнив
операцию сворачивания с помощью третьего правила, получим цепочку a b <B> x. Теперь выполним сворачивание с помощью
второго правила и получим цепочку a <B> x.
Наконец, выполним сворачивание с использованием первого правила. Получим
начальный символ грамматики, следовательно, заданная цепочка принадлежит языку,
порождаемому заданной грамматикой.
Если схема грамматики содержит много правил, и если задана длинная
цепочка, то процедура сворачивания становится трудоемкой, поскольку после
каждого сворачивания нужно многократно просматривать цепочку, чтобы определить,
какие из правил можно применить на очередном шаге сворачивания. Если можно
применить несколько правил, то следует принять решение, какое из правил выбрать
для выполнения операции. Может возникнуть ситуация, когда на очередном шаге
нельзя применить ни одно из правил. В этом случае нужно выбрать другое правило
и повторить попытку.
Существенно то, что для некоторых классов контекстно – свободных
грамматик и для автоматных грамматик эту процедуру удается существенно
упростить и, более того, построить устройства, выполняющие процедуру
распознавания автоматически. Такие устройства в общем случае называют распознавателями. Соответствие между автоматными
грамматиками и распознавателями рассматривается в настоящей главе. В ней
обсуждаются проблемы построения распознавателей для грамматик автоматного типа.
Такие распознаватели в литературе часто называют автоматами без выходного
преобразователя или просто автоматами без выходов. Вначале приводится определение
автоматного распознавателя и обсуждается возможности построения
детерминированных распознавателей такого типа. Затем рассматриваются способы
построения распознавателей для конечных языков и приемы минимизици и числа
состояний без выходов.