Методические указания к курсовой работе по дисциплине «Теория языков программирования и методы трансляции» (стр. 2 из 4)
Полученный автомат является неполностью определенным (частичным), поскольку в таблице переходов (табл. 3) есть незаполненные клетки, и, кроме того, недетерминированным, поскольку в той же таблице есть клетки, содержащие пары состояний.
Чтобы получить полностью определенный автомат, следует ввести дополнительное состояние Er (ошибка). Для этого нужно дополнить автомат соответствующей строкой с состоянием Er и во все пустые клетки таблицы переходов вписать это состояние Er (см. табл. 4).
Таблица 4
Таблица переходов недетерминированного полностью определенного автомата
| x0 | x2 | x3 | x4 | x5 | x6 | x7 | ||
| S | Er | Er | Er | Er | S1,S3 | F | C | 0 |
| S1 | Er | Er | Er | Er | Er | S2 | Er | 0 |
| S2 | A | Er | Er | Er | Er | Er | Er | 0 |
| S3 | Er | Er | Er | Er | Er | S4 | Er | 0 |
| S4 | Er | Er | Er | B | Er | Er | Er | 0 |
| A | Er | D | Er | Er | A1 | Er | Er | 0 |
| A1 | Er | Er | Er | Er | Er | Er | Er | 1 |
| B | Er | E | Er | Er | B1 | Er | Er | 0 |
| B1 | Er | Er | Er | Er | Er | Er | Er | 1 |
| C | Er | E | Er | Er | C1 | Er | Er | 0 |
| C1 | Er | Er | Er | Er | Er | Er | Er | 1 |
| D | Er | S | D1 | Er | Er | Er | Er | 0 |
| D1 | Er | Er | Er | Er | Er | Er | Er | 1 |
| E | Er | S | E1 | Er | Er | Er | Er | 0 |
| E1 | Er | Er | Er | Er | Er | Er | Er | 1 |
| F | Er | F9 | Er | Er | F5 | Er | F1 | 0 |
| F1 | Er | Er | Er | Er | F2 | Er | Er | 0 |
| F2 | Er | Er | Er | F3 | Er | Er | Er | 0 |
| F3 | F4 | Er | Er | Er | Er | Er | Er | 0 |
| F4 | Er | Er | Er | Er | Er | Er | Er | 1 |
| F5 | Er | Er | Er | Er | F6 | Er | Er | 0 |
| F6 | Er | Er | Er | F7 | Er | Er | Er | 0 |
| F7 | F8 | Er | Er | Er | Er | Er | Er | 0 |
| F8 | Er | Er | Er | Er | Er | Er | Er | 1 |
| F9 | Er | Er | Er | Er | Er | Er | F10 | 0 |
| F10 | F11 | Er | Er | Er | Er | Er | Er | 0 |
| F11 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Er | Er | Er | Er | Er | Er | Er | Er | 0 |
Граф переходов автомата, построенный по таблице 4, показан на рис. 1.
Рис. 1. Граф переходов исходного (недетерминированного) автомата
Примечание. Для того чтобы не затемнять картину, на рисунке опущены дуги, исходящие из недопускающих состояний и ведущие в состояние Er (ошибка). Так, например, опущена дуга, ведущая из состояния S в состояние Er, которая должна быть помечена дизъюнкцией входных символов x0Úx2Úx3Úx4.
Все дуги, ведущие из допускающих состояний в состояние Er, должны быть помечены дизъюнкцией x0Úx2Úx3Úx4Úx5Úx6Úx7.
Нетрудно убедиться, что построенный автомат допускает все те и только те цепочки символов, которые принадлежат языку L(G'), порождаемому грамматикой G'.
5. СВЕДЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА К ДЕТЕРМИНИРОВАННОМУ
Процедура построения детерминированного автомата Ад, эквивалентного недетерминированному автомату Ан, задается следующими шагами:
1. Пометить первую строку таблицы переходов для Ад множеством начальных состояний автомата Ан. Применить к этому множеству шаг 2.
2. По данному множеству состояний В, помечающему строку таблицы переходов автомата Ад, для которой переходы еще не вычислены, вычислить те состояния автомата Ан, которые могут быть достигнуты из В с помощью каждого входного символа х, и поместить полученные множества состояний в соответствующие ячейки таблицы для автомата Ад. Символически это выражается так: если d – функция недетерминированных переходов, то функция детерминированных перехода d' задается формулой d'(B, x) = {S | S Î d (T, x), " Т Î В}
3. Для каждого нового множества, порожденного переходами на шаге 2, посмотреть, имеется ли уже в Ад строка, помеченная этим множеством. Если нет, то создать новую строку и пометить ее этим множеством. Если множество уже использовалось как метка, никаких действий не требуется.
4. Если в таблице автомата Ад есть строка, для которой еще не вычислены переходы, вернуться назад и применить к этой строке шаг 2. Если все переходы вычислены, перейти к шагу 5.
5. Пометить строку как допускающее состояние автомата Ад тогда и только тогда, когда она содержит допускающее состояние недетерминированного автомата. В противном случае пометить как отвергающее состояние.
Описанная процедура гарантирует, что детерминированный автомат не содержит недостижимых состояний.
В результате применения этого алгоритма от недетерминированного автомата (табл. 4, рис. 1) можно перейти к эквивалентному детерминированному автомату, таблица переходов которого приведена в таблице 5.
Таблица 5
Таблица переходов детерминированного автомата.
| x0 | x2 | x3 | x4 | x5 | x6 | x7 | ||
| {S} | {Er} | {Er} | {Er} | {Er} | {S1,S3} | {F} | {C} | 0 |
| {S1,S3} | {Er} | {Er} | {Er} | {Er} | {Er} | {S2,S4} | {Er} | 0 |
| {S2,S4} | {A} | {Er} | {Er} | {B} | {Er} | {Er} | {Er} | 0 |
| {A} | {Er} | {D} | {Er} | {Er} | {A1} | {Er} | {Er} | 0 |
| {A1} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 1 |
| {B} | {Er} | {E} | {Er} | {Er} | {B1} | {Er} | {Er} | 0 |
| {B1} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 1 |
| {C} | {Er} | {E} | {Er} | {Er} | {C1} | {Er} | {Er} | 0 |
| {C1} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 1 |
| {D} | {Er} | {S} | {D1} | {Er} | {Er} | {Er} | {Er} | 0 |
| {D1} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 1 |
| {E} | {Er} | {S} | {E1} | {Er} | {Er} | {Er} | {Er} | 0 |
| {E1} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 1 |
| {F} | {Er} | {F9} | {Er} | {Er} | {F5} | {Er} | {F1} | 0 |
| {F1} | {Er} | {Er} | {Er} | {Er} | {F2} | {Er} | {Er} | 0 |
| {F2} | {Er} | {Er} | {Er} | {F3} | {Er} | {Er} | {Er} | 0 |
| {F3} | {F4} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 0 |
| {F4} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 1 |
| {F5} | {Er} | {Er} | {Er} | {Er} | {F6} | {Er} | {Er} | 0 |
| {F6} | {Er} | {Er} | {Er} | {F7} | {Er} | {Er} | {Er} | 0 |
| {F7} | {F8} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 0 |
| {F8} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 1 |
| {F9} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {F10} | 0 |
| {F10} | {F11} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 0 |
| {F11} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 1 |
| {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 0 |
Перейдем к более простым обозначениям состояний автомата:
{S}®Y; {S1,S3}®Y1; {S2,S4}®Y2;
{A}®Y3; {A1}®Y4; {B}®Y5; {B1}®Y6;
{C}®Y7; {C1}®Y8; {D}®Y9; {D1}®Y10;
{E}®Y11; {E1}®Y12; {F}®Y13; {F1}®Y14;
{F2}®Y15; {F3}®Y16; {F4}®Y17; {F5}®Y18;
{F6}®Y19; {F7}®Y20; {F8}®Y21; {F9}®Y22;
{F10}®Y23; {F11}®Y24; {Er}®Er.
В новых обозначениях таблица переходов автомата приведена в табл. 6.
Таблица 6
Таблица переходов детерминированного автомата
(новые обозначения состояний)
| x0 | x2 | x3 | x4 | x5 | x6 | x7 | ||
| Y | Er | Er | Er | Er | Y1 | Y13 | Y7 | 0 |
| Y1 | Er | Er | Er | Er | Er | Y2 | Er | 0 |
| Y2 | Y3 | Er | Er | Y5 | Er | Er | Er | 0 |
| Y3 | Er | Y9 | Er | Er | Y4 | Er | Er | 0 |
| Y4 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Y5 | Er | Y13 | Er | Er | Y6 | Er | Er | 0 |
| Y6 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Y7 | Er | Y11 | Er | Er | Y8 | Er | Er | 0 |
| Y8 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Y9 | Er | Y | Y10 | Er | Er | Er | Er | 0 |
| Y10 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Y11 | Er | Y | Y12 | Er | Er | Er | Er | 0 |
| Y12 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Y13 | Er | Y22 | Er | Er | Y18 | Er | Y14 | 0 |
| Y14 | Er | Er | Er | Er | Y15 | Er | Er | 0 |
| Y15 | Er | Er | Er | Y16 | Er | Er | Er | 0 |
| Y16 | Y17 | Er | Er | Er | Er | Er | Er | 0 |
| Y17 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Y18 | Er | Er | Er | Er | Y19 | Er | Er | 0 |
| Y19 | Er | Er | Er | Y20 | Er | Er | Er | 0 |
| Y20 | Y21 | Er | Er | Er | Er | Er | Er | 0 |
| Y21 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Y22 | Er | Er | Er | Er | Er | Er | Y23 | 0 |
| Y23 | Y24 | Er | Er | Er | Er | Er | Er | 0 |
| Y24 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Er | Er | Er | Er | Er | Er | Er | Er | 0 |
Граф переходов автомата, построенный по таблице 6, показан на рис. 2.