Специальная математика. Соловьев А.Е. - 44 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

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

Рубрика: 

- I - эквивалентные
Т.П. 1 2 3 4 5 6
x
1
1/A 3/A 6/B 2/A 6/B 4/A
x
2
2/A 1/A 3/A 2/A 5/A 5/A
- II - эквивалентные
A B A B C
A B C
Т.П. 1 2 4 3 5 6
x
1
1/A 3/A 6/B 2/C 6/C 4/A
x
2
2/A 1/A 3/A 2/B 5/B 5/B
- III - эквивалентные
A B C
Т.П. A B C
x
1
A C A
x
2
A B B
Т.В. A B C
x
1
y
1
y
1
y
2
x
2
y y
2
y
2
Получен минимальный (с точностью до изоморфизма) автомат, в котором классы
эквивалентных состояний заменены именами классов. Он эквивалентен (по поведению)
исходному автомату, но имеет три состояния вместо шести.
Замечание. Классы, в процессе их выделения, могут дробиться, но не могут объединяться.
Ограниченность метода Гилла. В полученном автомате наглядно видно, что автомат не
выйдет из начального состояния А – оно является тупиковым. Следовательно, автомат
никогда не перейдет в состояния В и С, которые в данном случае будут недостижимыми.
Анализ тупиковых и недостижимых состояний может повлиять на конфигурацию
минимального автомата, либо (что скорее всего) выявить ошибки в его построении.
Однако метод Гилла, как и большинство других методов минимизации, не учитывает
влияния тупиковых и недостижимых состояний на результирующий автомат.
3.4. Особенности минимизации автомата Мура
Минимизация автомата Мура отличается первым шагом. Здесь в классы одно-
эквивалентных попадают состояния, отмеченные одинаковыми выходными сигналами.
А В
y
1
y
2
y
2
y
2
y
2
y
2
y
2
1 2 3 4 5 6 7
x
1
2/B 3/B 5/B 3/B 4/B 7/B 3/B
x
2
1/А 1/А 1/А 1/А 1/А 1/А 1/А
— 44 —
                                                - I - эквивалентные
Т.П. 1   2   3   4   5   6
x1   1/A 3/A 6/B 2/A 6/B 4/A
x2   2/A 1/A 3/A 2/A 5/A 5/A
                                                - II - эквивалентные
          A             B     A       B     C

               A                  B         C

Т.П. 1   2   4   3   5   6
x1   1/A 3/A 6/B 2/C 6/C 4/A
x2   2/A 1/A 3/A 2/B 5/B 5/B
                                                - III - эквивалентные
               A                  B         C

Т.П. A    B        C
x1   A    C        A
x2   A    B        B

Т.В. A    B        C
x1   y1   y1       y2
x2   y    y2       y2

Получен минимальный (с точностью до изоморфизма) автомат, в котором классы
эквивалентных состояний заменены именами классов. Он эквивалентен (по поведению)
исходному автомату, но имеет три состояния вместо шести.
Замечание. Классы, в процессе их выделения, могут дробиться, но не могут объединяться.
Ограниченность метода Гилла. В полученном автомате наглядно видно, что автомат не
выйдет из начального состояния А – оно является тупиковым. Следовательно, автомат
никогда не перейдет в состояния В и С, которые в данном случае будут недостижимыми.
Анализ тупиковых и недостижимых состояний может повлиять на конфигурацию
минимального автомата, либо (что скорее всего) выявить ошибки в его построении.
Однако метод Гилла, как и большинство других методов минимизации, не учитывает
влияния тупиковых и недостижимых состояний на результирующий автомат.

                    3.4. Особенности минимизации автомата Мура

Минимизация автомата Мура отличается первым шагом. Здесь в классы одно-
эквивалентных попадают состояния, отмеченные одинаковыми выходными сигналами.


               А                                            В


          y1                y2            y2       y2           y2      y2    y2
          1                 2             3        4            5       6     7
x1        2/B               3/B           5/B      3/B          4/B     7/B   3/B
x2        1/А               1/А           1/А      1/А          1/А     1/А   1/А


                                                 — 44 —

Страницы