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

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

1. S  x6 x4 x4 A 9. C  x0 E

2. S  x6 x6 x2 B 10. C  x4

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

4. S  x7 F 12. D  x0

5. A  x0 D 13. E  x4 S

6. A  x4 14. E  x0

7. B  x0 E 15. F  x1 x2 x5 x1

8. B  x4 16. F  x4 x2 x5 x1

17. F  x6 x7 x1.

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

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

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  x6 S1 16. D  x0

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

3. S2 x4 A 18. E  x0

4. S  x6 S3 19. F  x1 S5

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

6. S4x2 B 21. S6 x5 S7

7. S  x5 C 22. S7 x1

8. S  x7 F 23. Fx4 S6

9. A  x0 D 24. F  x6 S8

10. А  x4 25. S8  x7 S7.

11. B  x0E

12. B  x4

13. C  x0 E

14. C  x4

15. D  x4 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 (нач. сост.)					q15	q3	q7 ,q9	q6
q1	A	q4				q15
q2	B	q5				q15
q3	C	q5				q15
q4	D	q15				q0
q5	E	q15				q0
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 . В итоге, получаем таблицу 4:

Таблица 4

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