Переход от праволинейной грамматики к автоматной
Таблица 4. Таблица переходов недетерминированного полностью определенного автомата. Таблица 3. Таблица переходов недетерминированного частичного автомата. Граф переходов автомата, построенный по таблице 4, показан на рис. 1. Рис. 1. Граф переходов исходного (недетерминированного) автомата. Fx6 F1; F1x3 F2; F2x7 F3; F3x1 F4; F4; Fx0 F5; F5x3 F6; F6x7 F7; F7x1 F8; F8; Fx5 F9; F9x5 F10; F10×1 F11… Читать ещё >
Переход от праволинейной грамматики к автоматной (реферат, курсовая, диплом, контрольная)
Этот этап выполняется путем расширения нетерминального словаря способом, вытекающим из возможности преобразования праволинейной грамматики в модифицированную автоматную G''=< V't, V''n, S, R''>. Таким образом получим множество R'' правил вывода:
Sx2 S1; S1x1 S2; S2x7 A;
Sx2 S3; S3x3 S4; S4x0 B;
Sx6 C;
Sx7 F;
Ax7 D; Ax4 A1; A1;
Bx7 E; Bx4 B1; B1;
Cx7 E; Cx4 C1; C1;
Dx2 S; Dx5 D1; D1;
Ex2 S; Ex5 E1; E1;
Fx6 F1; F1x3 F2; F2x7 F3; F3x1 F4; F4;
Fx0 F5; F5x3 F6; F6x7 F7; F7x1 F8; F8;
Fx5 F9; F9x5 F10; F10×1 F11; F11.
Таким образом, нетерминальный словарь теперь имеет вид V''n = {S, S1, S2, S3, S4, A, A1, B, B1, C, C1, D, D1, E, E1, F, F1, F2, F3, F4, F5, F6, F7, F8, F9, F10, F11} и его мощность |V''n| равна 27.
ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА
Построим на основе грамматики G'' конечный автомат. При этом нетерминальным символам грамматики V''n поставим в соответствие состояния автомата (оставим для них те же обозначения). Начальному нетерминалу S поставим в соответствие начальное состояние автомата S. Правилам вывода поставим в соответствие переходы автомата. В результате получим таблицу 3 — таблицу переходов недетерминированного конечного автомата, соответствующего рассматриваемому примеру.
Таблица 3. Таблица переходов недетерминированного частичного автомата.
x0. | x1. | x2. | x3. | x4. | x5. | x6. | x7. |
S. | S1,S3. | C. | F. | ||||
S1. | S2. | ||||||
S2. | A. | ||||||
S3. | S4. | ||||||
S4. | B. | ||||||
A. | A1. | D. | |||||
A1. | |||||||
B. | B1. | E. | |||||
B1. | |||||||
C. | C1. | E. | |||||
C1. | |||||||
D. | S. | D1. | |||||
D1. | |||||||
E. | S. | E1. | |||||
E1. | |||||||
F. | F5. | F9. | F1. | ||||
F1. | F2. | ||||||
F2. | F3. | ||||||
F3. | F4. | ||||||
F4. | |||||||
F5. | F6. | ||||||
F6. | F7. | ||||||
F7. | F8. | ||||||
F8. | |||||||
F9. | F10. | ||||||
F10. | F11. | ||||||
F11. |
Полученный автомат является не полностью определенным (частичным), поскольку в таблице переходов (табл. 3) есть незаполненные клетки, и, кроме того, недетерминированным, поскольку в той же таблице есть клетки, содержащие пары состояний.
Чтобы получить полностью определенный автомат, следует ввести дополнительное состояние Er (ошибка). Для этого нужно дополнить автомат соответствующей строкой с состоянием Er и во все пустые клетки таблицы переходов вписать это состояние Er (см. табл. 4).
Таблица 4. Таблица переходов недетерминированного полностью определенного автомата.
x0. | x1. | x2. | x3. | x4. | x5. | x6. | x7. | ||
S. | Er. | Er. | S1,S3. | Er. | Er. | Er. | C. | F. | |
S1. | Er. | S2. | Er. | Er. | Er. | Er. | Er. | Er. | |
S2. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | A. | |
S3. | Er. | Er. | Er. | S4. | Er. | Er. | Er. | Er. | |
S4. | B. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | |
A. | Er. | Er. | Er. | Er. | A1. | Er. | Er. | D. | |
A1. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | |
B. | Er. | Er. | Er. | Er. | B1. | Er. | Er. | E. | |
B1. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | |
C. | Er. | Er. | Er. | Er. | C1. | Er. | Er. | E. | |
C1. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | |
D. | Er. | Er. | S. | Er. | Er. | D1. | Er. | Er. | |
D1. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | |
E. | Er. | Er. | S. | Er. | Er. | E1. | Er. | Er. | |
E1. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | |
F. | F5. | Er. | Er. | Er. | Er. | F9. | F1. | Er. | |
F1. | Er. | Er. | Er. | F2. | Er. | Er. | Er. | Er. | |
F2. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | F3. | |
F3. | Er. | F4. | Er. | Er. | Er. | Er. | Er. | Er. | |
F4. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | |
F5. | Er. | Er. | Er. | F6. | Er. | Er. | Er. | Er. | |
F6. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | F7. | |
F7. | Er. | F8. | Er. | Er. | Er. | Er. | Er. | Er. | |
F8. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | |
F9. | Er. | Er. | Er. | Er. | Er. | F10. | Er. | Er. | |
F10. | Er. | F11. | Er. | Er. | Er. | Er. | Er. | Er. | |
F11. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | |
Er. | Er. | Er. | Er. | Er. | Er. | Er. | Er. | Er. |
Далее построим граф переходов (Рис. 1), при этом в нем опустим состояния исходящие из недопускающих состояний и ведущие в состояние Er (ошибка).
Граф переходов автомата, построенный по таблице 4, показан на рис. 1.
Рис. 1. Граф переходов исходного (недетерминированного) автомата
Примечание. Для того чтобы не затемнять картину, на рисунке опущены дуги, исходящие из недопускающих состояний и ведущие в состояние Er (ошибка). Так, например, опущена дуга, ведущая из состояния S в состояние Er, которая должна быть помечена дизъюнкцией входных символов x0x1x2x3x4.
Все дуги, ведущие из допускающих состояний в состояние Er, должны быть помечены дизъюнкцией x0x1x2x3x4x5x6x7.