Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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


Задание автоматов

 

Автоматы могут быть заданы следующими способами:

1. В виде графа


 

 

 

 


РИС. 5.1. Автомат Мили

 

РИС. 5.2. Автомат Мура.

 

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

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

2. В виде таблиц перехода и выхода (автомат Мили); отмеченной таблицы перехода (автомат Мура).

Автомат Мили описывается с помощью двух таблиц: таблицы перехода и таблицы выхода:

 

Таблица переходов (ТП) Таблица выходов (ТВ)

     
 
 

 


Автомат Мура описывается с помощью отмеченной таблицы перехода:

Таблица переходов (ТП)

 
 

ПРИМЕР.

Синтезировать автомат, на вход которого подаются монеты номинальной стоимостью 1, 2 и 3 копейки, а на выходе автомат выдает билет, если сумма набранных монет составляет 3 копейки, если сумма меньше 3 копеек, то автомат ничего не выдает, если сумма больше 3 копеек, то автомат возвращает деньги.

Определим входной, выходной алфавиты и множество внутренних состояний:

· входной алфавит - монеты номинальной стоимостью 1, 2 и 3 копейки

· выходной алфавит - на выходе возможны выходные символы: - ничего;- билет;- возврат.

· множество внутренних состояний ,

где - начальное состояние автомата « в автомате ничего нет»;

- «в автомате 1 копейка»;

- «в автомате 1 копейка»;

- «в автомате 2 копейки»;

- «в автомате 3 копейки».

Граф автомата имеет вид:

 

 

РИС. 5.3. Автомат Мили



 

Таблицы перехода и выхода представлены в виде:

Таблица переходов (ТП) Таблица выходов (ТВ)

     
  Н Н Б Н
  Н Б В Н
  Б В В Б

 

Неопределенным состоянием называется несуществующее состояние.

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

 

Входным словом называется совокупность сигналов, поступающих на вход.

Выходным словом называются совокупность сигналов на выходе.

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

Два состояния одноэквивалентными, если на одинаковое входное слово выдается одинаковый выходной сигнал.

Два состояния k-эквивалентными, если на одинаковое входное слово длиной в k-единиц выдается одинаковый выходной сигнал длиной в k-единиц.

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

Эквивалентные состояния объединяются в класс эквивалентности.

Минимальный автоматэто автомат, состоящий из наименьшего числа состояний, каждое из которых является классом эквивалентности исходного автомата.

 

<== предыдущая лекция | следующая лекция ==>
Законы функционирования автоматов | Алгоритм минимизации автомата Мили

Дата добавления: 2014-01-04; Просмотров: 235; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.006 сек.