Грамматика Автоматная

Грамматика конечно-автоматная, грамматика с конечным числом состояний,- грамматика бесконтекстная, каждое правило к-рой имеет вид или где — вспомогательные символы, а — один из основных символов. (Иногда допускаются также правила вида где — пустая цепочка; класс порождаемых языков при этом расширяется только за счет языков, получаемых из прежних добавлением цепочки Л.) Для каждой Г. а. можно построить эквивалентный ей автомат конечный. Класс языков, порождаемых Г. а. (автоматных языков), совпадает (при допущении правил с пустой правой частью) с классом регулярных множеств. Автоматные языки образуют собственный подкласс класса линейных языков (см. Грамматика линейная);так, линейный язык — не автоматный. Класс автоматных языков замкнут относительно объединения, пересечения, умножения, подстановки и усеченной итерации (а при наличии правил с пустой правой частью также и относительно итерации). Пересечение бесконтекстного языка с автоматным есть бесконтекстный язык. Для наглядного изображения Г. а. используется д и-аграмма — ориентированный мультиграф, вершинами к-рого служат вспомогательные символы, и из вершины Ав вершину Видет дуга, помеченная (основным) символом а, если в грамматике есть правило кроме того, в диаграмме имеется еще одна вершина — заключительная, в к-рую из вершины — вспомогательного символа А — идет дуга, помеченная символом а, если в Г. а. есть правило (При наличии правил вида каждый символ А , для к-рого имеется такое правило, также считается заключительной вершиной.) Цепочка в основном словаре выводима в грамматике из вспомогательного символа Атогда и только тогда, когда она "запи сана" на нек-ром пути в диаграмме, идущем из Ав заключительную вершину. На рис. изображена диаграмма Г. а. с правилами (I — начальный символ, К — заключительная вершина), порождающей язык Лит.:[1] Гладкий А. В., Формальные грамматики и языки, М., 1973; [2] Трахтенброт Б. А., Барздинь Я. М., Конечные автоматы (Поведение и синтез), М., 1970. А. В. Гладкий.