2. Построение и преобразование грамматик

На основе использования табл.1 и 2 составляется грамматика индивидуальная для конкретного студента. Например,

1. S  x5 x4 x2 A 9. C  x2E

2. S  x5 x7 x1 B 10. C  x5

3. S  x0 C 11. D  x5 S

4. S  x6 F 12. D  x1

5. A  x2 D 13. E  x5 S

6. A  x5 14. E  x1

7. B  x2 E 15. F  x2 x6 x0 x0

8. B  x5 16. F  x5 x6 x0 x0

17. F  x7 x2 x0.

Грамматика называется праволинейной, если правая часть каждого правила содержит не более одного нетерминала, причем этот нетерминал является самым правым символом.

Грамматика называется автоматной, если ее правила имеют вид:

A  x B ; A  x , где x  V , В  W.

Для сведения праволинейной грамматики к автоматной используют следующий прием (в качестве примера возьмем одно из правил приведенной выше грамматики, а именно, правило S -> x7 x0 x1 A). Перепишем левую часть правила и первый слева символ правой части, а оставшуюся от правой части цепочку обозначим новым нетерминальным символом, который дополнительно будет вводиться в грамматику, например , S1. В результате получим следующее новое правило:

S  x7 S1; S1  x0 x1 A.

Затем, аналогичным способом преобразуем правило для S1 (получим правила вида S1  x0 S2 и S2  x1 A). Правило S2 не требует дальнейших преобразований, так как оно удовлетворяет требованиям правил автоматной грамматики.

Данным образом преобразуются все правила грамматики, которые имеют в правой части цепочку терминальных символов.

Продолжим пример. Из праволинейной грамматики, записанной выше, получаем автоматную грамматику G’ с правилами вывода вида:

1. S  x5 S1 16. D  x1

2. S1 x4 S2 17. E  x5 S

3. S2 x2 A 18. E  x1

4. S  x5 S3 19. F  x2 S5

5. S3 x7 S4 20. S5x6 S6

6. S4x1 B 21. S6 x0 S7

7. S  x0 C 22. S7 x0

8. S  x6 F 23. Fx5 S6

9. A  x2 D 24. F  x7 S8

10. А  x5 25. S8  x2 S7.

11. B  x2 E

12. B  x5

13. C  x2 E

14. C  x5

15. D  x5 S

3. Построение детерминированного конечного автомата

Для автоматной грамматики строится таблица переходов недетерминированного автомата (в таблице по строкам расположены состояния, а по столбцам - входные символы, в клетках на пересечении i-й строки и j-го столбца проставляется состояние, в которое переходит автомат из состояния i по приходу входного символа j ). Для этого каждому нетерминалу ставится в соответствие некоторое состояние автомата. Затем по грамматике таблица заполняется следующим образом: на пересечении строки состояния, соответствующего нетерминалу левой части правила, и столбца, соответствующего терминальному символу, ставится состояние, соответствующее нетерминальному символу правой части правила. Если нетерминал в правой части отсутствует, то в клетке таблицы ставится заключительное состояние, которое вводится дополнительно к уже имеющимся состояниям.

Приведение недетерминированного автомата

к детерминированному виду

Детерминированным конечным автоматом называется конечный автомат, любая клетка таблицы переходов которого не содержит несколько состояний. В пустой клетке подразумеваем состояние ошибки.

Процедура приведения недетерминированного конечного автомата к детерминированному (по таблице переходов) сводится к следующему:

1. Определяется клетка, в которой содержится 2 или более состояний

( например, qi и qj).

2. Строка i и строка j накладываются друг на друга, и в таблице переходов появляется новая склеенная строка, соответствующая новому состоянию q_{i, j}.

3. Если состояние qi или qj стоит отдельно или в комбинации с другими состояниями еще в какой-либо клетке таблицы, то соответствующая строка i или j сохраняется в таблице, иначе - убирается из таблицы после склеивания.

Продемонстрируем изложенное на примере:

Таблица 3

	Состояние	x0	x1	x2	x3	x4	x5	x6		x7
q0	S (нач. сост.)	q3						q6		q7, q9
q1	A									q4, q15
q2	B								q5, q15
q3	C									q5, q15
q4	D					q0	q15
q5	E					q0	q15
q6	F						q11			q12, q14
q7	S1	q8
q8	S2		q1
q9	S3				q10
q 10	S4									q2
q 11	S5		q12
q 12	S6						q13
q 13	S7							q15
q 14	S8		q13
q 15	закл. сост.

Склеиваем состояния q7 и q9 в состояние q7,9 ( см. строку q0 и столбец X7 ). Удаляем из таблицы строку состояния q9, так как на состояние q9 нет больше переходов. Cтроку состояния q7 заменяем на склеенную строку q7,9, так как на состояние q7 нет больше переходов. Аналогично склеиваем состояния q4 и q15 в состояние q4,15 (cм. строку q4 и столбец X7). Заменяем строку состояния q4 на состояние q4,15, так как на состояние q4 нет больше переходов. Не удаляем из таблицы строку состояния 15, так как на состояние 16 есть ссылки в таблице переходов. Склеиваем состояния q5 и q15 в состояние q5,15 ( см. строку q2 и столбец X7 ). Заменяем строку q5 на строку q5,16. Склеиваем строки состояний q12 и q14 в одну строку с состоянием q12,14 путем наложения строк. А строку q14 удаляем из таблицы, так как на состояние q14 нет других ссылок в таблице переходов. В итоге, получаем таблицу 4:

Таблица 4

	x0	x1	x2	x3	x4	x5	x6		x7
q0 нач.сост.	q3						q6		q7, 9
q1									q4, 15
q2								q5,15
q3									q5,15
q4,15					q0	q15
q5,15					q0	q15
q6						q11			q12, 14
q7,9	q8			q10
q8		q1
q 10									q2
q 11		q12
q 12						q13
q 13							q15
q12,14		q13				q13
q 15 закл. сост