ГРАММАТИКА АВТОМАТНАЯ

ГРАММАТИКА АВТОМАТНАЯ, грамматика конечно-автоматная, грамматика с конечным числом состояний, - грамматика бесконтекстная, каждое правило к-рой имеет вид А → аВ или А → a, где А, В - вспомогательные символы, а - один из основных символов. (Иногда допускаются также правила вида A → Λ, где Λ - пустая цепочка; класс порождаемых языков при этом расширяется только за счет языков, получаемых из прежних добавлением цепочки Λ.) Для каждой Г. а. можно построить эквивалентный ей автомат конечный. Класс языков, порождаемых Г. а. (автоматных языков), совпадает (при допущении правил с пустой правой частью) с классом регулярных множеств. Автоматные языки образуют собственный подкласс класса линейных языков (см. Грамматика линейная); так, линейный язык {aⁿbⁿ| n = 1, 2, ...} - не автоматный. Класс автоматных языков замкнут относительно объединения, пересечения, умножения, подстановки и усеченной итерации (а при наличии правил с пустой правой частью также и относительно итерации). Пересечение бесконтекстного языка с автоматным есть бесконтекстный язык.

Для наглядного изображения Г. а. используется диаграмма - ориентированный мультиграф, вершинами к-рого служат вспомогательные символы, и из вершины А в вершину В идет дуга, помеченная (основным) символом а, если в грамматике есть правило A → аВ; кроме того, в диаграмме имеется еще одна вершина - заключительная, в к-рую из вершины - вспомогательного символа А - идет дуга, помеченная символом а, если в Г. а. есть правило A → a. (При наличии правил вида A → Λ каждый символ А, для к-рого имеется такое правило, также считается заключительной вершиной.) Цепочка в основном словаре выводима в грамматике из вспомогательного символа А тогда и только тогда, когда она «записана» на нек-ром пути в диаграмме, идущем из А в заключительную вершину. На рис. изображена диаграмма Г. а. с правилами I → aI, I → aB, B → bB, B → b (I - начальный символ, K - заключительная вершина), порождающей язык {аⁿb^m| n, m = 1, 2, ...}.

Лит.: [1] Гладкий А. В., Формальные грамматики и языки, М., 1973; [2] Трахтенброт Б. А., Барздинь Я. М., Конечные автоматы (Поведение и синтез), М., 1970.

А. В. Гладкий.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.