Теория автоматов. - 15 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Рубрика: 

Определим далее 4-эквивалентные классы (табл. 21). 3-эквивалентные классы
совпали с 4-эквивалентными, следовательно, мы получили классы эквивалент-
ных состояний. Минимальный автомат будет иметь вид табл. 22 и 23.
0 1 2 3 4 5 6
х
1
1
b
3
c
4
c
6
d
6
d
6
d
6
d
х
2
2
b
4
c
5
c
4
c
5
c
3
c
0
a
Таблица 21
Таблица 22 Таблица 23
7.2. Минимальный автомат будет иметь вид табл.24, 25.
Таблица 24 Таблица 25
Отметим, что при различном кодирование классов эквивалентности
можно получить не абсолютно одинаковые, а изоморфные (т.е. одинаковые с
точностью до имен состояний) автоматы.
8.1. 1-эквивалентные классы определяются по первой строке отмеченной
таблицы переходов, 2-эквивалентные – на основе содержания этой таблицы
(табл.26).
y
1
y
1
y
1
y
1
y
1
y
1
y
1
1 2 3 4 5 6 7
a b c d
х
1
b c d d
х
2
b c c a
a b c d
х
1
y
1
y
3
y
1
y
1
х
2
y
2
y
2
y
2
y
2
a b c d e
α c d a a b
β c c c e e
γ b a c d b
a b c d e
α 1 1 0 0 0
β 1 1 1 1 1
γ 1 1 1 1 1
a b c d
a b
a b c d 
Определим далее 4-эквивалентные классы (табл. 21). 3-эквивалентные классы
совпали с 4-эквивалентными, следовательно, мы получили классы эквивалент-
ных состояний. Минимальный автомат будет иметь вид табл. 22 и 23.
                      a       b         c       d

                                0               1           2       3       4        5              6
                                1               3           4       6       6        6              6
                       х1
                                    b               c           c       d       d           d            d
                                2               4           5       4       5        3              0
                       х2
                                    b               c           c       c       c           c            a

                                    a                       b            c                           d
                                                                Таблица 21

                   a        b               c           d                                       a            b       c    d

            х1     b        c               d           d                           х1          y1           y3      y1   y1

            х2     b        c               c           a                           х2          y2           y2      y2   y2

                   Таблица 22                                                                        Таблица 23


         7.2. Минимальный автомат будет иметь вид табл.24, 25.

            a     b         c           d           e                                               a         b       c    d   e
     α      c     d         a           a           b                                α              1         1       0    0   0
     β      c     c         c           e           e                                β              1            1    1    1   1
     γ      b     a         c           d           b                                   γ           1         1       1    1   1

                 Таблица 24                                                                                  Таблица 25

       Отметим, что при различном кодирование классов эквивалентности
можно получить не абсолютно одинаковые, а изоморфные (т.е. одинаковые с
точностью до имен состояний) автоматы.
       8.1. 1-эквивалентные классы определяются по первой строке отмеченной
таблицы переходов, 2-эквивалентные – на основе содержания этой таблицы
(табл.26).

                                                            a                       b

                                y1 y1 y1 y1 y1 y1 y1

                                1           2       3           4   5       6        7

Страницы