Пособие ДМ2

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

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

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

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

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

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

Данный акцептор принимает, в частности следующие строки как 001, 0001, 100, 1010, 10110.

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

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

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

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

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

е

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

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

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

При

нять

Y

b

с

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

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

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

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

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

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

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

2.6.1. Не полностью описанные (частичные) автоматы

В определении конечного автомата (A, S, B, , ) предполагается, что функции и всюду определены.

Однако на практике, встречаются случаи, когда они лишь частично определены. Это связано с тем, что сложные системы проектируются по частям и поэтому может оказаться, что некоторые входящие строки либо вообще не встречаются, либо встречаются в случаях, когда выход нас не интересует. Это приводит к тому, что некоторые позиции в таблицах состояний (или ребра в диаграммах состояний) отсутствуют. Также позиции называются безразличными, т.к. нас не интересуют их содержания. В таблицах состояний они обозначается прочерками.

Например, в таблице