Синтез распознающего автомата

Курсовой проект - Компьютеры, программирование

Другие курсовые по предмету Компьютеры, программирование

p>) D -> x2 S;

.1)D -> x2 D1;

.2)D1 -> ?;

) E -> x2 S;

.1)E -> x2 E1;

.2)E1 -> ?;

.1)F -> x6 F1;

.2)F1 -> x2 F2;

.3)F2 -> x4 F3;

.4) F3 -> x6 F4;

.5)F4 -> ?;

.1)F -> x7 F5;

.2)F5 -> x2 F5;

.3)F6 -> x4 F6;

.4)F7 -> x6 F8;

.5)F8 -> ?;

.1)F -> x3 F9;

.2)F9 -> x0 F10;

.3)F10 -> x6 F11;

.4)F11 -> ?;

 

 

4. ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА

 

Процедуру построения недетерминированного автомата по автоматной грамматике:

1)Входным множеством автомата будет терминальное множество грамматики;

2)Множеством состояний автомата будет нетерминальное множество грамматики, а в качестве начального состояния будет выступать начальный нетерминальный символ грамматики - S;

)По правилам 6.2, 8.2, 10.2, 12.2, 14.2, 15.5, 16.5, 17.4 состояния A1, B1, C1, D1, E1, F4, F8, F11 будут допускающими;

)Для всех правил грамматики по правилу A xB вводим в автомате переход из состояния A в состояние B по входу x;

)Чтобы получить полностью определенный автомат, вводим состояние ошибки - Err, и во все оставшиеся клетки записываем переход в состояние ошибки.

Результатом такого построения является недетерминированный автомат с одним начальным состоянием и с одним допускающим состоянием. Таблицей переходов полученного автомата является таблица 3.

 

Таблица 3 Таблица переходов недетерминированного автомата

x0x1x2x3x4x5x6x7SErrFErrCErrS1, S3ErrErr0S1S2ErrErrErrErrErrErrErr0S2ErrErrErrErrAErrErrErr0S3ErrErrErrErrErrS4ErrErr0S4ErrErrErrErrBErrErrErr0AErrErrErrErrA1ErrErrD0A1ErrErrErrErrErrErrErrErr1BErrErrErrErrB1ErrErrE0B1ErrErrErrErrErrErrErrErr1CErrErrErrErrC1ErrErrE0C1ErrErrErrErrErrErrErrErr1DErrSErrErrErrD1ErrErr0D1ErrErrErrErrErrErrErrErr1EErrSErrErrErrE1ErrErr0E1ErrErrErrErrErrErrErrErr1FErrErrErrF9ErrF5F1Err0F1ErrErrF2ErrErrErrErrErr0F2ErrErrErrErrF3ErrErrErr0F3ErrErrErrErrErrErrF4Err0F4ErrErrErrErrErrErrErrErr1F5ErrErrF6ErrErrErrErrErr0F6ErrErrErrErrF7ErrErrErr0F7ErrErrErrErrErrErrF8Err0F8ErrErrErrErrErrErrErrErr1F9F10ErrErrErrErrErrErrErr0F10ErrErrErrErrErrErrErrErr0F11ErrErrErrErrErrErrF11Err1ErrErrErrErrErrErrErrErrErr0

Построим граф переходов недетерминированного автомата (рис. 2). Для облегчения читаемости графа не отображено состояние ошибки и переходы из всех состояний недетерминированного автомата в состояние ошибки по оставшимся входным символам.

 

 

Граф переходов недетерминированного автомата S

Рис. 2

 

 

5. СВЕДЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА К ДЕТЕРМИНИРОВАННОМУ

 

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

Обозначения:

АН - недетерминированный автомат;

АД - эквивалентный ему, детерминированный автомат.

Процедура построения АД по АН:

. Пометить первую строку таблицы переходов для АД множеством начальных состояний автомата АН.

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

. Для каждого нового множества, порожденного на шаге 2, посмотреть: имеется ли уже в АД строка, помеченная этим множеством, если нет, то создать новую строку и пометить ее этим множеством. Если множество уже использовалось как метка, то никаких действий не надо.

. Если в таблице АД есть строка, для которой еще не вычислены переходы, то вернуться назад и применить к этой строке шаг 2. Если все переходы вычислены, то переходим к шагу 5.

. Пометить строку как допускающее состояние АД, тогда и только тогда, когда она содержит допускающее состояние АН, иначе пометить как отвергающее.

Добавим состояние ошибки R и во всех пустых клетках запишем переход в состояние ошибки. Получим детерминированный автомат таблицей переходов которого является таблица 4.

Таблица 4 Таблица переходов детерминированного автомата

x0x1x2x3x4x5x6x7SErrFErrCErr{S1,S3}ErrErr0{S1,S3}S2ErrErrErrErrS4ErrErr0S2ErrErrErrErrAErrErrErr0S4ErrErrErrErrBErrErrErr0AErrErrErrErrA1ErrErrD0A1ErrErrErrErrErrErrErrErr1BErrErrErrErrB1ErrErrE0B1ErrErrErrErrErrErrErrErr1CErrErrErrErrC1ErrErrE0C1ErrErrErrErrErrErrErrErr1DErrSErrErrErrD1ErrErr0D1ErrErrErrErrErrErrErrErr1EErrSErrErrErrE1ErrErr0E1ErrErrErrErrErrErrErrErr1FErrErrErrF9ErrF5F1Err0F1ErrErrF2ErrErrErrErrErr0F2ErrErrErrErrF3ErrErrErr0F3ErrErrErrErrErrErrF4Err0F4ErrErrErrErrErrErrErrErr1F5ErrErrF6ErrErrErrErrErr0F6ErrErrErrErrF7ErrErrErr0F7ErrErrErrErrErrErrF8Err0F8ErrErrErrErrErrErrErrErr1F9F10ErrErrErrErrErrErrErr0F10ErrErrErrErrErrErrErrErr0F11ErrErrErrErrErrErrF11Err1ErrErrErrErrErrErrErrErrErr0

Построим граф переходов детерминированного автомата (рис. 3). Для облегчения читаемости графа не отображено состояние ошибки и переходы из всех состояний детерминированного автомата в состояние ошибки по оставшимся входным символам.

детерминированный автомат праволинейный грамматика

Граф переходов детерминированного автомата

Рис. 3

 

6. ПОСТРОЕНИЕ МИНИМАЛЬНОГО АВТОМАТА

 

Для получения минимального автомата воспользуемся методом разбиения. Метод разбиения заключается в разбиении множества состояний на непересекающиеся подмножества (блоки), такие, что неэквивалентные состояния попадают в разные блоки.

Условия эквивалентности состояний:

условие подобия: состояния S и T должны быть либо оба допускающими, либо оба отвергающими;

условие преемственности: для всех входных символов состояния S и T должны переходить в эквивалентные состояния, т.е. их преемники эквивалентны.

Сначала состояния разбиваются на 2 блока. Один содержит только допускающие, другой - отвергающие. Очевидно, никакое из состояний 1-го блока не эквивалентно ни одному состоянию второго блока, что следует из условия подобия. Затем происходит разбиение этих блоков на более мелкие по следующему алгоритму:

). Если под действием какого-либо входного символа какая-то часть состояний данного блока п?/p>