Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 37 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

37
Где K
1
= {A , В},
Σ
1
= {0,1}, S
1
= {А}, f
1
= {В},
а переходы представлены в таблице 6.2 и на рис.6.2:
Таблица 6.2
Состояния
А В
0 Ø {В}
Вход
1 {A,В}{B}
A
B
1
1
0,1
Рис.6.2. Переходы недетерминированного конечного автомата M
1
.
Первая строка будет принята, так как имеется переход
(последовательность переходов), ведущий к последнему состоянию при
чтении строки. Имеется также переход к непоследнему состоянию, но это не
влияет на приемлемость строки. Поэтому прежде чем прийти к выводу о том,
что строка не может быть принята недетерминированным конечным
автоматом, необходимо перепробовать
все возможные последовательности
переходов.
Существует детерминированный конечный автомат М
2
,
соответствующий автомату М
1
, который принимает тот же язык. Переходы
автомата М
2
приведены в таблице 6.3 и на рис.6.3.
M
2
= (K
2
,
Σ
2
,
δ
2
, S
2
, f
2
), где K
2
= {A , В , C},
Σ
2
= {0,1}, S
2
= {А}, f
2
= {В}
Таблица 6.3
Состояния
А В C
0 C В C
Вход
1 В B C 
                                                                                        37
Где K1 = {A , В}, Σ 1= {0,1}, S1 = {А}, f1= {В},
а переходы представлены в таблице 6.2 и на рис.6.2:

                                            Таблица 6.2
                                     Состояния
                                                А       В
                             Вход      0        Ø       {В}
                                       1    {A,В} {B}


                                1                              0,1

                                A                             B
                                             1
      Рис.6.2. Переходы недетерминированного конечного автомата M1.


      Первая     строка     будет     принята,      так       как    имеется     переход
(последовательность переходов), ведущий к последнему состоянию при
чтении строки. Имеется также переход к непоследнему состоянию, но это не
влияет на приемлемость строки. Поэтому прежде чем прийти к выводу о том,
что строка не может быть принята недетерминированным конечным
автоматом, необходимо перепробовать все возможные последовательности
переходов.
      Существует        детерминированный               конечный       автомат       М2,
соответствующий автомату М1, который принимает тот же язык. Переходы
автомата М2 приведены в таблице 6.3 и на рис.6.3.
      M2 = (K2, Σ2, δ2, S2 , f2 ), где K2 = {A , В , C}, Σ2= {0,1}, S2 = {А}, f2= {В}
                                            Таблица 6.3
                                     Состояния
                                            А       В     C
                             Вход     0     C       В     C
                                      1     В       B     C

Страницы