2.5.5. Автоматные грамматики

Рассмотрим языки, которые «принимаются» или «распознаются» автоматами с конечным числом состояний. Такой автомат после считывания символа из состояния s переходит в новое состояние . Считав последний символ, автомат останавливается. Если он остановился в одном из «принимающих» состояний из отмеченного множества F, входная строка считается принятой. Если конечное состояние автомата лежит в , то строка считается отвергнутой. Рассмотрим формальное определение.

Акцептором с конечным числом состояний (конечным акцептором, анализатором) называется пятерка , где:

- конечное множество входных символов,

- конечное множество внутренних состояний,

- функция из в ,

– начальное состояние

- множество принимающих состояний, где .

Входные символы линейно упорядочены, так как они напечатаны на входной ленте, и последовательно считываются читающей головкой. Пример конечного акцептора, заданного с помощью графа.

Рис. 9

Данный акцептор принимает, такие строки как 001, 0001, 100, 1010, 10110.

Рассмотрим класс грамматики, порождающих в точности такие множества строк, которые принимаются некоторым конечным акцептором.

Определение. Автоматной грамматикой называется четверка , где

– конечное множество входных символов,

– конечное множество терминальных символов,

– конечное множество правил порождения вида ,

– отмеченный начальный символ.

Небольшие конечные акцепторы, а также автоматные грамматики, удобно изображать с помощью диаграмм состояний.

Для составления диаграммы состояний автоматной грамматики – следует произвести следующие действия:

Шаг 1. Каждому нетерминальному символу из постaвить в соответствие вершину графа.

Шаг 2. Каждому правилу поставить в соответствие дугу от вершины к вершине, помеченную символом b.

Шаг 3. Каждому правилу поставить в соответствие дугу от вершины к новой вершине, с пометкой ПРИНЯТЬ.

Пример. На рисунке показана диаграмма состояний (помеченный ориентированный граф), отвечающая автоматной грамматике G с правилами.

X

Рис. 10

Для автоматных грамматик справедливы утверждения.

1. Последовательность меток дуг вдоль любого конечного пути, начинающегося из вершины А, на диаграмме грамматики G, является строкой, порождаемой G, и, наоборот, все порождаемые строки соответствуют некоторым путям.

2. Для любой автоматной грамматики существует конечный акцептор, принимающий в точности те строки, которые порождает грамматика.

3. Для любого конечного акцептора существует автоматная грамматика, порождающая в точности те строки, которые принимаются этим акцептором.

4. Существуют контекстно-свободные языки, не являющиеся автоматными языками.

2.6. Модификации конечных автоматов

Существуют многочисленные модификации конечных автоматов. С одной из них мы уже знакомились – это машины Тьюринга. Рассмотрим модификации, связанные с обобщениями переходной и выходной функций. Для них допускается произвольные отношения, случайные функции и т.п. В частности, к таким модификациям относятся частичные, недетерминированные и вероятные автоматы.