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

UptoLike

ВУЗ: 

ПНИПУ | Пермь

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

Рубрика: 

1,3
2
2
Пример 2 (автомат Мура).
Построить автомат, на вход которого могут поступать монеты 1, 2, 3 коп. Автомат выдает
сигнал “чет”, если поступившая сумма в данный момент четная и “нечет”, если наоборот.
чет нечет
Это автомат Мура. Поэтому выходные сигналы приписаны не стрелкам, а к состояниям,
которыми они однозначно определяются. Табличное представление сводится к одной
таблице – расширенной таблице переходов. В ней добавляется верхняя строка,
позволяющая приписать выходные сигналы состояниям.
Чет Нечет
Ч Н
1 Н Ч
2 Ч Н
3 Н Ч
3.3. Минимизация автоматов
Автоматы различной конфигурации могут реализовывать одну и ту же функцию. Для
практических целей важно уметь находить автомат с минимальным количеством состояний,
реализующий заданное поведение. Число состояний абстрактного автомата определяет при
практической реализации число необходимых элементов памяти.
Кстати, первый рассмотренный автомат был (сознательно) построен избыточным. От
состояния q
3
очень просто избавиться, передав его функции состоянию q
0
.
Существуют различные методы минимизации. К числу простейших относится Метод Гилла,
позволяющий отыскивать классы эквивалентных состояний и заменять их отдельными
состояниями.
Два автомата называются эквивалентными, если они имеют одинаковые входные и
выходные алфавиты, и на одинаковые входные слова выдают одинаковые выходные слова
(одинаковой длины).
Два состояния называются 1-эквивалентными, если они не различимы с помощью одного
входного сигнала (символа).
Состояния называются k-эквивалентными, если начиная с них неразличимы входные слова
длиной в k.
Если состояния k-эквивалентные для любого k, то они называются эквивалентными.
Рассмотрим минимизацию методом Гилла на каком-то конкретном автомате Мили.
Т.В. 1 2 3 4 5 6
x
1
y
1
y
1
y
1
y
1
y
1
y
2
x
2
y
2
y
2
y
2
y
2
y
2
y
2
A B
— 43 —
1,3
Ч Н
-
в
ы
Пример 2 (автомат Мура).
 Построить автомат, на вход которого могут поступать монеты 1, 2, 3 коп. Автомат выдает
сигнал “чет”, если поступившая сумма в данный момент четная и “нечет”, если наоборот.



     2                           1,3

                   Ч             1,3         Н          2
                  чет                       нечет

Это автомат Мура. Поэтому выходные сигналы приписаны не стрелкам, а к состояниям,
которыми они однозначно определяются. Табличное представление сводится к одной
таблице – расширенной таблице переходов. В ней добавляется верхняя строка,
позволяющая приписать выходные сигналы состояниям.

 -       Чет Нечет
в
ы        Ч   Н
1        Н   Ч
2        Ч   Н
3        Н   Ч

                                       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


                                                     — 43 —

Страницы