ГРАММАТИКА АВТОМАТНАЯ это:

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

грамматика конечно-автоматная, грамматика с конечным числом состояний,- грамматика бесконтекстная, каждое правило к-рой имеет вид или где - вспомогательные символы, а - один из основных символов. (Иногда допускаются также правила вида где - пустая цепочка; класс порождаемых языков при этом расширяется только за счет языков, получаемых из прежних добавлением цепочки Л.) Для каждой Г. а. можно построить эквивалентный ей автомат конечный. Класс языков, порождаемых Г. а. (автоматных языков), совпадает (при допущении правил с пустой правой частью) с классом регулярных множеств. Автоматные языки образуют собственный подкласс класса линейных языков (см. Грамматика линейная);так, линейный язык - не автоматный. Класс автоматных языков замкнут относительно объединения, пересечения, умножения, подстановки и усеченной итерации (а при наличии правил с пустой правой частью также и относительно итерации). Пересечение бесконтекстного языка с автоматным есть бесконтекстный язык.

Для наглядного изображения Г. а. используется д и-аграмма - ориентированный мультиграф, вершинами к-рого служат вспомогательные символы, и из вершины Ав вершину Видет дуга, помеченная (основным) символом а, если в грамматике есть правило кроме того, в диаграмме имеется еще одна вершина - заключительная, в к-рую из вершины - вспомогательного символа А - идет дуга, помеченная символом а, если в Г. а. есть правило (При наличии правил вида каждый символ А , для к-рого имеется такое правило, также считается заключительной вершиной.) Цепочка в основном словаре выводима в грамматике из вспомогательного символа Атогда и только тогда, когда она "запи сана" на нек-ром пути в диаграмме, идущем из Ав заключительную вершину. На рис. изображена диаграмма Г. а. с правилами (I - начальный символ, К - заключительная вершина), порождающей язык


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


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "ГРАММАТИКА АВТОМАТНАЯ" в других словарях:

  • ГРАММАТИКА БЕСКОНТЕКСТНАЯ — грамматика контекстно свободная, КС грамматика, грамматика составляющих, все правила к рой имеют вид где А вспомогательный символ и непустая цепочка (так наз. бесконтекстные правила). Языки, порождаемые такими грамматиками, наз. бесконтекстными… …   Математическая энциклопедия

  • ГРАММАТИКА ПОРОЖДАЮЩАЯ — грамматика Хомского, один из видов формальной грамматики;представляет собой, по существу, частный случай исчисления Поста (см. Поста каноническая система). Систематич. изучение Г. п. было начато в 50 х гг. 20 в. Н. Хомскнм (N. Chomsky), к рый… …   Математическая энциклопедия

  • ГРАММАТИКА ЛИНЕЙНАЯ — грамматика бесконтекстная, у к рой правая часть каждого правила содержит не более одного вхождения вспомогательного символа. Класс порождаемых такими грамматиками языков (линейных языков) является собственным подклассом класса бесконтекстных… …   Математическая энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»