Синтез распознающего автомата
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?й грамматики представлен на рис. 1.
Рис. 1. Граф грамматики G
3.ПОСТРОЕНИЕ АВТОМАТНОЙ ГРАММАТИКИ ПО ПРАВОЛИНЕЙНОЙ
Процедура перевода праволинейной грамматики в автоматную состоит из следующих пунктов:
1.Если имеется правила вида Аw, где w - непустая терминальная цепочка, то ввести новый нетерминальный символ В и добавить правило Вe. Затем заменить каждое из правил вида Aw правилом AwB.
2.Заменить каждое правило вида Aa1...anB, для n>1, на правила:
Aa1A1
A1a2A2
...n-1anAn,
где: Ai, для (1 < i< (n-1)) - новые нетерминальные символы.
3.Если имеется правила вида АB, то, во-первых, удалить правила BB (если таковые имеются), во-вторых, заменить их правилами вида: Aa, для всех A и a, для которых существуют правила AB и Ba.
Применив данную процедуру перевода к полученной праволинейной грамматике G, получим следующую автоматную грамматику:
4. ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА
Процедуру построения недетерминированного автомата по автоматной грамматике:
1.Входным множеством автомата будет терминальное множество грамматики;
2.Множеством состояний автомата будет нетерминальное множество грамматики, а в качестве начального состояния будет выступать начальный нетерминальный символ грамматики - S;
.По правилу Z e состояние Z будет допускающим;
.Для всех правил грамматики по правилу A xB вводим в автомате переход из состояния A в состояние B по входу x
.Чтобы получить полностью определенный автомат, вводим состояние ошибки - Er, и во все оставшиеся клетки записываем переход в состояние ошибки.
Результатом такого построения является недетерминированный автомат с одним начальным состоянием. Таблицей переходов полученного автомата является таблица 3.
Таблица 3. Недетерминированный конечный автомат
x0x 1x 2x 3x 4x 5x 6x 7SErErCErErS1FErC0S1ErS2ErErErErErEr0S2ErErErErErErErA0S3ErErS4ErErErErEr0S4ErErErErErErBEr0AErErZErErErDEr0ZErErErErErErErEr1BErErZErErErEEr0CErErZErEErEEr0DErErErErSErZEr0EErErErErSErZEr0FErF4ErErErErF7F1 0F1ErErErF2ErErErEr0F2F3ErErErErErErEr0F3ErErErErErZErEr0F4ErErErF5ErErErEr0F5F6ErErErErErErEr0F6ErErErErErErZEr0F7ErErErErErErErF80F8ErErErErErZErEr0ErErErErErErErErEr05.
6.СВЕДЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА К ДЕТЕРМИНИРОВАННОМУ
Процедура перехода от недетерминированного автомата к детерминированному:
Обозначения:
АД - детерминированный автомат
АН - недетерминированный автомат
. Пометить первую строку таблицы переходов для АД множеством начальных состояний автомата АН.
. По данному множеству состояний B, помечающему строку таблицы переходов автомата АД, для которой переходы еще не выполнены, вычислить те состояния АН, которые могут быть достигнуты из B с помощью каждого входного символа и поместить полученное множество состояний в состояние ячейки для автомата АД.
. Для каждого нового множества, порожденного на шаге 2, посмотреть: имеется ли уже в АД строка, помеченная этим множеством, если нет, то создать новую строку и пометить ее этим множеством. Если множество уже использовалось как метка, то никаких действий не надо.
. Если в таблице АД есть строка, для которой еще не вычислены переходы, то вернуться назад и применить к этой строке шаг 2. Если все переходы вычислены, то переходим к шагу 5.
. Пометить строку как допускающее состояние АД, тогда и только тогда, когда она содержит допускающее состояние АН, иначе пометить как отвергающее.
. Добавим состояние ошибки Er и во всех пустых клетках запишем переход в состояние ошибки.
Получим следующий детерминированный автомат (см. табл. 4).
Таблица 4. Детерминированный автомат
x 0x 1x 2x4x 5x 6x 7{S}{Er}{Er}{C}{Er}{ S1F }{Er}{C}0{F}{Er}{F4}{Er}{Er}{F1}{ F7}{F1 }0{C}{Er}{Er}{Z}{E}{Er}{ E }{Er}0{S1 S3}{Er}{ S2}{ S4}{ Er } {Er}{ Er }{Er}0{F7 }{Er}{ Er }{Er}{Er}{Er}{Er}{ F8}0{F4}{Er}{ F5}{Er}{Er}{Er}{Er}{Er}0{F1 }{Er}{ F2}{Er}{Er}{Er}{Er}{Er}0{Z}{Er}{Er}{Er}{Er}{Er}{Er}{Er}1{E}{Er}{ Er }{Er}{ S }{ Er }{ Z }{Er}0{S4 }{Er}{Er}{Er}{Er}{Er}{ B }{ Er }0{S2 }{Er}{Er}{Er}{Er}{Er}{Er}{ A }0{F8 }{Er}{Er}{Er}{Er}{ Z }{ Er }{Er}0{F2 }{Er}{ F3}{Er}{Er}{ Er }{Er}{Er}0{B}{Er}{Er}{ Z }{ Er }{Er}{ E }{Er}0{A}{Er}{Er}{ Z }{ Er }{Er}{ D }{Er}0{F3 }{Er}{Er}{Er}{Er}{ Z }{ Er }{Er}0{D}{Er}{ Er }{Er}{ S }{ Er }{ Z }{Er}0{F5 }{ F6}{Er}{Er}{Er}{ Er }{Er}{Er}0{F6 }{Er}{Er}{Er}{Er}{Er}{ Z }{Er}0{Er}{Er}{Er}{Er}{Er}{Er}{Er}{Er}0
. ПОСТРОЕНИЕ МИНИМАЛЬНОГО АВТОМАТА
Для получения минимального автомата воспользуемся методом разбиения. Метод разбиения заключается в разбиении множества состояний на непересекающиеся подмножества (блоки), такие, что неэквивалентные состояния попадают в разные блоки.
Условия эквивалентности состояний:
- Условие подобия: состояния S и T должны быть либо оба допускающими, либо оба отвергающими.
- Условие преемственности: для всех входных символов состояния S и T должны переходить в эквивалентные состояния, т.е. их преемники эквивалентны.
Сначала состояния разбиваются на 2 блока. Один содержит только допускающие, другой - отвергающие. Очевидно, никакое из состояний 1-го блока не эквивалентно ни одному состоянию второго блока, что следует из условия подобия. Затем происходит разбиение этих блоков на более мелкие по следующему алгоритму:
. Если под действием какого-либо входного символа какая-то часть состояний данного блока переходит в состояния из другого блока, что нарушает условие преемственности, то необходимо разбить данный блок на части так, чтобы не нарушалось в одном блоке условие преемственности.
2. Необходимо повторять шаг 1 до тех пор, пока дальнейшее разбиение невозможно.
3. За один раз можно разбить только один блок.
Обозначим {S1S3} за {Y}.
.1 Делим на группы допускающих, недопускающих состояний
P0={{S, Y, S2, S4, A, B, C, D, E, F, F1, F2, F3, F4, F5, F6, F7, F8}, {Z}}
.2 Разбиваем по входу x2:1={{A, B, C}, {S, Y, S2, S4, D, E, F, F1, F2, F3, F4, F5, F6, F7, F8},{Z}}
.3 Ра