Geum.ru

Специальная математика

Вид материалаКонспект

Содержание


3.3. Минимизация автоматов
Метод Гилла
Подобный материал:
1   ...   10   11   12   13   14   15   16   17   ...   39

3.3. Минимизация автоматов



Автоматы различной конфигурации могут реализовывать одну и ту же функцию. Для практических целей важно уметь находить автомат с минимальным количеством состояний, реализующий заданное поведение. Число состояний абстрактного автомата определяет при практической реализации число необходимых элементов памяти.

Кстати, первый рассмотренный автомат был (сознательно) построен избыточным. От состояния q3 очень просто избавиться, передав его функции состоянию q0.

Существуют различные методы минимизации. К числу простейших относится Метод Гилла, позволяющий отыскивать классы эквивалентных состояний и заменять их отдельными состояниями.

Два автомата называются эквивалентными, если они имеют одинаковые входные и выходные алфавиты, и на одинаковые входные слова выдают одинаковые выходные слова (одинаковой длины).

Два состояния называются 1-эквивалентными, если они не различимы с помощью одного входного сигнала (символа).

Состояния называются k-эквивалентными, если начиная с них неразличимы входные слова длиной в k.

Если состояния k-эквивалентные для любого k, то они называются эквивалентными.

Рассмотрим минимизацию методом Гилла на каком-то конкретном автомате Мили.



Т.В.
1
2
3
4
5
6

x1
y1
y1
y1
y1
y1
y2

x2
y2
y2
y2
y2
y2
y2




A B


- 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


Получен минимальный (с точностью до изоморфизма) автомат, в котором классы эквивалентных состояний заменены именами классов. Он эквивалентен (по поведению) исходному автомату, но имеет три состояния вместо шести.

Замечание. Классы, в процессе их выделения, могут дробиться, но не могут объединяться.

Ограниченность метода Гилла. В полученном автомате наглядно видно, что автомат не выйдет из начального состояния А – оно является тупиковым. Следовательно, автомат никогда не перейдет в состояния В и С, которые в данном случае будут недостижимыми.

Анализ тупиковых и недостижимых состояний может повлиять на конфигурацию минимального автомата, либо (что скорее всего) выявить ошибки в его построении.

Однако метод Гилла, как и большинство других методов минимизации, не учитывает влияния тупиковых и недостижимых состояний на результирующий автомат.