Автоматные грамматики и конечные автоматы

Автоматную грамматику можно представить в виде таблицы, где строки соответствуют терминалам, а столбцы нетерминалам. На пересечении строки a и столбца A записываются нетерминалы B, которые входят в правила A ® aB. На рис. 3.1 представлена таблица переходов, построенная для А-грамматики из примера 1.9. Приведенная таблица представляет собой ничто иное, как функциональную таблицу или таблицу переходов конечного автомата.

Конечный автомат - это частный случай одностороннего распознавателя, где головка движется всегда вправо на каждом такте работы и отсутствует внешняя память.

Конечный автомат M можно определить пятеркой множеств

M = {Q, S, d,q₀, F},

где

Q - конечное множество состояний автомата (при построении автоматов оно обычно совпадает с множеством нетерминалов грамматики);

S - конечное множество символов внешнего алфавита (конечное множество допустимых входных символов, совпадающих с множеством терминалов);

d - функция переходов, отображающая множество состояний и входных символов в множество состояний

Q´S®Q

и представляемая, обычно, в виде таблицы переходов (например, из таблицы с рис. 3.1 следует, что d (чис, +) = чбз, а d (дчп, Е) = пор);

q₀ - начальное состояние (на рис. 3.1 - чис);

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

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

Дата добавления: 2015-06-27