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

Страницы работы

Содержание работы

Ident

:

[a–zA–Z][0–9a–zA–Z]*

Const

:

[0–9]+([.][0–9]*)?

Const

:

[0–9]*[.][0–9]+

Formatting

:

[ \r\n\t]+

Operation

:

[–+*/]

Delimiter

:

[;]

Assign

:

[=]

 



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

Похожие материалы

Информация о работе