Преобразование недетерминированного неоптимального автомата в детерминированный оптимальный

 

	a–zA–Z	0–9a–zA–Z	0–9	.	\r\n\t	–+*/	;	=	ε
0	1		4, 9		14	15	16	17	18
1		2							3
2		2							3
3									19
4			4						5
5				6					20
6			7						8
7			7						8
8									20
9			9						10
10				11
11			12
12			12						13
13									20
14					14				21
15						15			22
16									23
17									24
18	Акцепт: EndOfFile
19	Акцепт: Ident
20	Акцепт: Const
21	Акцепт: Formatting
22	Акцепт: Operation
23	Акцепт: Delimiter
24	Акцепт: Assign

Преобразование недетерминированного неоптимального
автомата в детерминированный оптимальный

Критерии детерминированности и оптимальности:

1.  Множества символов, помечающие столбцы управляющей таблицы, попарно не пересекаются.

2.  Автомат не содержит недетерминированностей первого рода.

3.  Автомат не содержит недетерминированностей второго рода.

4.  Автомат не имеет тупиковых состояний.

5.  Автомат не имеет недостижимых состояний.

6.  Все рабочие состояния попарно не являются эквивалентными.

7.  В рабочей зоне управляющей таблице нет одинаковых столбцов.

8.  В рабочей зоне управляющей таблицы нет пустых клеток.

Критерий 1.

1.  Каждый столбец УТ, помеченный набором из n различных символов, превращается в nодинаковых столбцов, каждый из которых помечен одним символом.

2.  Если образовались одинаково помеченные столбцы, то они объединяются в один столбец:

k

k

k

k

m

k,m

 

	a-zA-Z	0-9a-zA-Z	0-9	…	a	b	…	z	A	B	…	Z	0	1	…	9	…
0	1		4,9	…	1	1	…	1	1	1	…	1	4,9	4,9	…	4,9	…
1		2			2	2	…	2	2	2	…	2	2	2	…	2
…