Как грамматики и автоматы описывают множества строк
Теория формальных языков и автоматов изучает множества строк и способы их задания или распознавания. Грамматики описывают правила порождения, а автоматы — вычислительные модели обработки строк; возможности модели зависят, в частности, от доступной памяти.
Формальные языки и автоматы
Конечные автоматы
Конечный автомат обрабатывает входную строку, переходя между состояниями из конечного множества. Детерминированные и недетерминированные конечные автоматы распознают один и тот же класс регулярных языков; отдельного неограниченного хранилища памяти у такой модели нет.
Магазинные автоматы
Магазинный автомат сочетает конечное управление со стеком, доступным по принципу «последним пришёл — первым вышел». Недетерминированные магазинные автоматы распознают контекстно-свободные языки; детерминированная разновидность обладает более ограниченными возможностями.
Формальные грамматики
Формальная грамматика задаёт язык через набор терминальных и нетерминальных символов, начальный символ и правила переписывания. Применение правил порождает строки языка; ограничения на форму правил определяют свойства грамматики и возможности её анализа.