Синтез распознающего автомата
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
выступать начальный нетерминальный символ грамматики - 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-го блока не эквивалентно ни одному состоянию второго блока, что следует из условия подобия. Затем происходит разбиение этих блоков на более мелкие по следующему алгоритму:
) Если под действием какого-либо входного символа какая-то часть состояний данного блока переходит в состояния из другого блока, что нарушает условие преемственности, то необходимо разбить данный блок на части так, чтобы не нарушалось в одном блоке условие преемственности.
) Необходимо повторять шаг 1 до тех пор, пока дальнейшее разбиение невозможно.
) За один раз можно разбить только один блок.
Обозначим {S1, S3} как {M}.
Поделим на группы допускающих, недопускающих состояний:
{{S, M, S2, S4, A, B, C, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err}, {A1, B1, C1, D1, E1, F4, F8, F11}}.
Разобьем {S, M, S2, S4, A, B, C, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err} повходуx4:
{{S, M, S2, S4, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err}, {A, B, C}, {A1, B1, C1, D1,