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

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

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

Скачать Бесплатно!
Для того чтобы скачать эту работу.
1. Пожалуйста введите слова с картинки:

2. И нажмите на эту кнопку.
закрыть



й грамматики представлен на рис. 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

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

 

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

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

  1. Условие подобия: состояния S и T должны быть либо оба допускающими, либо оба отвергающими.
  2. Условие преемственности: для всех входных символов состояния 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 Ра

s