Языки, порождаемые автоматными грамматиками, являются языками, принимаемыми соответствующими конечными автоматами.
Конечным автоматом (КА, конечным недетерминированным автоматом –КНА, конечным распознавателем) называют пятерку
A=(N, T, , S, F),
где
N–конечное множество состояний;
T– конечного множество входных символов (или множество терминальных символов грамматики, алфавит языка;
– функция переходов состояний (в общем случае неоднозначная);
SÎN– начальное состояние;
FÍN– множество заключительных состояний.
Недетерминированность конечного автомата заключается в возможной неоднозначности функции переходов. На некоторых тактах автомат может перейти не в одно, а сразу в несколько состояний. В результате чего получается несколько автоматов в различных состояниях, работающих синхронно.
Говорят, что автомат A принимает (допускает) цепочку, если после подачи на вход этой цепочки автомат переходит в одно из конечных состояний. Множество всех цепочек, переводящих автомат из начального состояния в одно из конечных состояний образует язык, принимаемый (допускаемый) этим автоматом. Если автомат А принимает язык, порождаемый грамматикой G, то
- множество состояний автомата А это множество нетерминальных символов грамматики G;
- множество входных символов автомата – это множество терминальных символов грамматики G, т.е алфавит языка;
- функция переходов автомата A задается правилами грамматики G;
- конечные состояния автомата A это такие нетерминальные символы K грамматик G, для которых существует правило вида K ®e;
- начальное состояние автомата A, это нецелевой символ грамматики G.
Дерево разбора в автоматной грамматике может быть однозначно построено, если задан КА. КА не только дает ответ на вопрос о принадлежности цепочки языку, но и позволяет выявить структуру цепочки. Правила вида A→a и A→e могут быть использованы в процессе порождения цепочки только один раз. Каждая подстановка вида A→aB приводит к появлению в дереве новой внутренней вершины, помеченной нетерминалом. Ее левая дочерняя вершина помечается терминалом.
