Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 14 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

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

Рубрика: 

14
Таблица 3.1 – Функция переходов конечного автомата M
F A B C D E F G
a B C B D F
b C D E E D G E
Рисунок 3.1 – Граф исходного конечного автомата М
Последовательность устранения недостижимых состояний КА имеет вид:
Q
0
= {A};
Q
1
= {A, B, C};
Q
2
= {A, B, C, D, E};
Q
3
= {A, B, C, D, E}; т.к. Q
2
= Q
3
, то Q
д
= {A, B, C, D, E}.
Q
н
= {F, G }; Q
′
= {A, B, C, D, E};
Z
′
= {D, E}.
Функция переходов автомата
M
′
представлена в таблице 3.2.
Таблица 3.2 - Функция переходов автомата
M
′
F A B C D E
a B C B
b C D E E D
Граф КА
M
′
после устранения недостижимых состояний представлен на
рисунке 3.2.
Рисунок 3.2 - Граф КА
M
′
после устранения недостижимых состояний
Алгоритм 3.2. Объединение эквивалентных состояний КА
Вход: КА ),,,,( ZHFTQM
′
′′
=
′
без недостижимых состояний.
Выход: минимальный КА ),,,,( ZHFTQM
′
′
′
′
′
′
=
′
′
.
b
b b
a
a
b
b
a
A
B
D
C
E
b
a b
b
a
b b
a
a
b
b
a
A
B
D
C
E
F
G
         Таблица 3.1 – Функция переходов конечного автомата M

     F           A                B                   C                           D           E               F   G
     a           B                                                                C           B               D   F
     b           C                D                   E                           E           D               G   E
                                                                  b
                                      a                                                   a
                                                  B                               D               F
                                                                  a
                              A                                               b       b       a       b
                                                                      a                   b       G
                                  b               C                               E
                                                              b

                     Рисунок 3.1 – Граф исходного конечного автомата М

         Последовательность устранения недостижимых состояний КА имеет вид:
         Q0 = {A};
         Q1 = {A, B, C};
         Q2 = {A, B, C, D, E};
         Q3 = {A, B, C, D, E}; т.к. Q2 = Q3, то Qд = {A, B, C, D, E}.
         Qн = {F, G }; Q′ = {A, B, C, D, E}; Z ′ = {D, E}.
         Функция переходов автомата M ′ представлена в таблице 3.2.
         Таблица 3.2 - Функция переходов автомата M ′
             F            A                   B                           C               D               E
             a            B                                                               C               B
             b            C                   D                           E               E               D
     Граф КА M ′ после устранения недостижимых состояний представлен на
рисунке 3.2.
                                                      b
                              a
                                          B                           D
                                                      a
                      A                                           b           b
                                                          a
                          b               C                           E
                                                  b

          Рисунок 3.2 - Граф КА M ′ после устранения недостижимых состояний

            Алгоритм 3.2. Объединение эквивалентных состояний КА
         Вход: КА M ′ = (Q′, T , F ′, H , Z ′) без недостижимых состояний.
         Выход: минимальный КА M ′′ = (Q′′, T , F ′′, H , Z ′′) .


14

Страницы