КАТЕГОРИИ:
Архитектура-(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)
Эквивалентность автоматов. Минимизация
|
|
|
|
Основные определения и способы задания
КОНЕЧНЫЕ АВТОМАТЫ
Основной рассматриваемый объект – конечный автомат (КА).
КА – это система (так называемая «пятерка») 
, состоящая из таких объектов:
– 
= 
– множество входных сигналов;
– 
= 
– множество выходных сигналов;
– 
= 
– множество внутренних состояний;
– 
– функция, которая отображает декартово произведение 
во множество внутренних состояний ;
– 
– функция, которая отображает декартово произведение во множество выходов .
Переход из одного состояния в другое осуществляется потактно. Пусть номер такта обозначен как t. Тогда 
, 
, 
.
Таким образом, 
– канонические уравнения для КА.
Пример. Если A и B – улицы, то 
{нажатие кнопки}, 
{генератор сигнала переключателя светофора движения на перекрестке улиц A и В} (рис. 4.1).
Рис. 4.1. Перекресток
Внутренние состояния: 
– движение по улице A; 
– движение по улице B; 
– пешеходный переход после движения по улице A; 
– пешеходный переход после движения по улице B.
Пусть алфавит выходов содержит буквы А, Б, П, тогда
|
| 
|
|
|
|
| K | П | П | Б | А |
| Г | Б | А | Б | А |
|
|
|
|
|
| K |
|
|
|
|
| Г |
|
|
|
|
Рис. 4.2 иллюстрирует графический способ задания автомата.
Рис. 4.2. Размеченный граф автомата регулирования перекрестка
Матричный способ заключается во введении матриц отношений 
и 
:
, где 
,где 
Тем самым заданы матрицы переходов
, 
и матрицы выходов
, 
.
Автоматное отображение сигналов задается следующим образом:
– 
– поступает сигнал 
;
– 
– поступает сигнал 
;
…
– 
– поступает сигнал 
.
При этом 
.
Таким образом, получаем отображение входного слова 
в выходное слово 
, а 
– расширенная функция перехода 
.
|
|
|
Свойства автоматного отображения:
1) 
;
2) 
.
Эти свойства называются свойствами (условиями) автоматности отображения.
Пример. 
(рис. 4.3).
Рис. 4.3. Размеченный граф отображения
Контрольное задание
Построить граф автомата, классифицировать состояния, продемонстрировать внешнее поведение для слова длиной 20 (табл. 4.1).
Таблица 4.1
Варианты задания
| Номер варианта |
|
|
|
|
| Номер варианта |
|
|
|
|
|
| 4/1 | 2/2 | 1/1 | 1/1 |
| 4/2 | 2/1 | 4/2 | 2/1 | ||
| 4/2 | 4/2 | 4/1 | 1/2 |
| 2/1 | 1/2 | 2/1 | 2/1 | ||
| 4/2 | 1/1 | 4/2 | 4/1 |
| 3/2 | 2/1 | 2/2 | 2/1 | ||
|
| 1/1 | 3/1 | 2/1 | 1/2 |
| 1/2 | 3/1 | 1/2 | 4/1 | ||
|
| 2/2 | 3/1 | 1/1 | 1/1 |
| 3/1 | 1/1 | 1/1 | 4/1 | ||
|
| 3/1 | 3/1 | 4/2 | 3/2 |
| 3/2 | 1/1 | 1/1 | 2/2 | ||
|
| 4/2 | 4/1 | 4/2 | 1/2 |
| 3/1 | 1/2 | 2/2 | 1/2 | ||
|
| 1/2 | 4/2 | 2/2 | 2/2 |
| 4/2 | 2/1 | 4/1 | 4/1 | ||
|
| 3/2 | 1/1 | 4/1 | 3/2 |
| 4/2 | 1/1 | 2/1 | 3/1 | ||
|
| 3/1 | 3/2 | 4/1 | 2/2 |
| 2/1 | 3/1 | 4/2 | 3/1 | ||
|
| 2/2 | 4/2 | 3/1 | 1/2 |
| 1/2 | 4/1 | 3/1 | 3/1 | ||
|
| 4/1 | 2/1 | 3/2 | 3/1 |
| 4/1 | 4/1 | 3/1 | 1/1 | ||
|
| 4/2 | 4/2 | 4/2 | 2/2 |
| 2/2 | 3/1 | 2/1 | 1/1 | ||
|
| 3/1 | 2/2 | 2/1 | 2/2 |
| 3/2 | 2/2 | 4/2 | 4/2 | ||
|
| 3/1 | 2/2 | 2/1 | 4/1 |
| 2/2 | 3/1 | 4/2 | 4/1 | ||
|
| 4/1 | 2/1 | 3/1 | 3/1 |
| 4/2 | 3/2 | 4/1 | 3/1 | ||
|
| 2/2 | 2/2 | 3/1 | 2/2 |
| 1/2 | 3/2 | 4/2 | 2/1 | ||
|
| 1/1 | 1/1 | 4/1 | 3/2 |
| 4/1 | 3/2 | 4/2 | 2/2 | ||
|
| 1/2 | 1/1 | 2/2 | 1/2 |
| 4/2 | 3/1 | 2/1 | 3/2 | ||
|
| 4/1 | 2/1 | 1/2 | 1/2 |
| 3/2 | 3/1 | 1/1 | 1/2 | ||
|
| 3/2 | 4/1 | 3/1 | 1/2 |
| 4/2 | 4/1 | 1/1 | 1/1 | ||
|
| 1/1 | 1/2 | 3/1 | 1/2 |
| 4/2 | 3/1 | 3/1 | 1/2 | ||
|
| 1/1 | 1/1 | 1/2 | 4/1 |
| 4/2 | 3/2 | 1/1 | 3/2 | ||
|
| 1/2 | 2/2 | 4/2 | 3/2 |
| 4/1 | 3/2 | 4/1 | 3/2 |
Окончание табл. 4.1
| Номер варианта |
|
|
|
|
| Номер варианта |
|
|
|
|
|
|
| 3/2 | 4/2 | 1/2 | 2/2 |
| 4/1 | 3/2 | 1/1 | 3/1 | ||
|
| 4/1 | 1/2 | 2/2 | 1/2 |
| 2/2 | 3/1 | 3/1 | 2/1 | ||
|
| 3/1 | 3/1 | 1/1 | 2/2 |
| 4/2 | 1/2 | 1/2 | 1/1 | ||
|
| 1/2 | 2/1 | 1/1 | 3/1 |
| 1/2 | 2/2 | 2/1 | 3/2 | ||
|
| 3/2 | 3/1 | 1/2 | 3/1 |
| 3/1 | 4/2 | 3/2 | 3/1 | ||
|
| 3/2 | 1/2 | 2/1 | 2/1 |
| 2/2 | 2/1 | 2/2 | 4/1 | ||
|
| 1/1 | 1/2 | 4/1 | 4/1 |
| 3/2 | 1/2 | 2/2 | 4/1 | ||
|
| 4/1 | 1/1 | 4/2 | 4/1 |
| 4/2 | 4/1 | 1/2 | 3/2 | ||
|
| 3/1 | 4/2 | 4/2 | 3/1 |
| 3/2 | 2/2 | 2/1 | 2/1 | ||
|
| 3/1 | 4/1 | 2/1 | 4/1 |
| 4/1 | 2/1 | 3/2 | 2/1 | ||
|
| 3/1 | 1/2 | 4/1 | 4/1 |
| 4/1 | 2/1 | 3/1 | 2/1 | ||
|
| 2/1 | 1/1 | 2/1 | 2/2 |
| 4/1 | 3/2 | 1/2 | 2/1 |
|
|
|
Рассмотрим два автомата:
,
.
Состояния 
из множества 
автомата 
и соответственно 
из множества 
автомата В называются неразличимыми, если 
.
Автоматы и 
называются неразличимыми, если для любого состояния 
существует состояние 
, такое, что 
, и наоборот, 
.
Рассмотрим изменения состояний и выходов автомата с изменением времени. На каждом такте подается входной сигнал (символ), преобразуется внутреннее состояние, возникает сигнал выхода. Рассмотрим следующий такт. Действия аналогичны:
, 
.
Итак, автомат преобразует слова (как и машина Тьюринга, частным случаем которой является конечный автомат).
Рассмотрим состояние 
автомата . Состояние 
называется достижимым из состояния , если существует такое слово 
, что 
. Достижимые состояния образуют класс достижимых состояний (рис. 4.4).
а б
Рис. 4.4. Достижимое состояние (а) и класс достижимых состояний (б)
Рассмотрим два автомата 
, 
и состояния 
. Автоматы называются эквивалентными, если 
Иными словами, автоматы называются эквивалентными, если для каждого состояния 
существует эквивалентное ему состояние автомата 
. Эквивалентные автоматы обладают одинаковым внешним поведением, т.е. на одинаковые входные слова выдают одинаковые внешние слова. Автоматы могут различаться сложностью внутренней структуры, например, мощностью множеств 
и 
. Среди всех эквивалентных автоматов имеется минимальный. Одной из основных задач является следующая: найти автомат, эквивалентный данному, но обладающий наименьшим количеством внутренних состояний. Такие задачи решаются последовательно путем выявления одного неразличимого состояния, двух неразличимых состояний,…, 
неразличимых состояний, которые объединяются в классы 
неразличимых состояний.
Пример:
| Автомат | Состояния | Классы состояний | |||||||||
| A | 
| 1,5,8 | |||||||||
| 6/1 | 6/2 | 1/2 | 5/2 | 6/1 | 6/2 | 8/2 | 6/1 | 6/2 | 
| 2,9 | |
| 3/1 | 7/1 | 3/2 | 3/2 | 7/1 | 7/2 | 7/2 | 4/1 | 4/1 | 
| 3,4,6,7 | |
| 6/2 | 3/2 | 9/1 | 2/1 | 6/2 | 6/1 | 2/1 | 6/2 | 4/2 | 
| – |
На начальном этапе отыскиваем классы -эквивалентных неразличимых состояний (при 
):
| A |
|
|
| Классы | |||||||
|
| 1,5,8 | ||||||||||
| 6/1 | 6/1 | 6/1 | 6/2 | 6/2 | ½ | 5/2 | 6/2 | 8/2 |
| 2,9 | |
| 3/1 | 7/1 | 4/1 | 7/1 | 4/1 | 3/2 | 3/2 | 7/2 | 7/2 |
| 3,4,7 | |
| 6/2 | 6/2 | 6/2 | 3/2 | 4/2 | 9/1 | 2/1 | 6/1 | 2/1 |
|
|
|
|
Приходим к автомату, внутренние состояния которого отождествляются с найденными классами эквивалентных состояний:
| ||||
| 3/1 | 3/2 | 1/2 | 4/2 | |
| 3/1 | 3/1 | 3/2 | 3/2 | |
| 3/1 | 3/2 | 2/1 | 4/1 |
У полученного и исходного автоматов внешнее поведение одинаково.
Контрольное задание
Воспользовавшись данными, приведенными в табл. 4.2, выполнить следующее:
а) построить граф для каждого из заданных автоматов (рекомендуется использовать VISIO);
б) минимизировать автоматы, построить графы, проверить правильность минимизаций на словах длиной 20;
в) установить, эквивалентны ли заданные автоматы, проверить на слове длиной 20.
Таблица 4.2
Варианты задания
| Номер варианта | А | В | ||||||||||||||||
| 8/1 | 8/2 | 8/1 | 5/2 | 8/1 | 3/2 | 1/2 | 8/2 | 8/2 | 4/2 | 7/2 | 4/2 | 2/1 | 4/2 | 4/2 | 3/1 | |||
| 7/1 | 6/1 | 4/1 | 7/2 | 6/1 | 6/2 | 7/2 | 6/2 | 4/1 | 1/1 | 2/1 | 6/1 | 5/2 | 6/1 | 3/1 | 2/2 | |||
| 8/2 | 7/2 | 8/2 | 2/1 | 8/2 | 2/1 | 9/1 | 8/1 | 4/2 | 7/1 | 1/1 | 1/1 | 1/2 | 1/1 | 1/1 | 1/2 |
Окончание табл. 4.2
| Номер варианта | А | В | ||||||||||||||||
| 3/1 | 3/2 | 3/2 | 5/2 | 3/1 | 1/2 | 8/2 | 3/1 | 3/2 | 6/2 | 7/2 | 6/2 | 6/2 | 7/2 | 7/1 | 7/2 | |||
| 6/1 | 7/1 | 7/2 | 6/2 | 7/1 | 6/2 | 7/2 | 4/1 | 4/1 | 1/2 | 1/1 | 4/2 | 3/2 | 3/1 | 3/1 | 1/2 | |||
| 3/2 | 6/2 | 3/1 | 2/1 | 3/2 | 9/1 | 2/1 | 3/2 | 4/2 | 5/1 | 4/2 | 2/1 | 2/1 | 1/2 | 7/2 | 7/1 | |||
| 3/2 | 8/1 | 7/1 | 2/2 | 3/2 | 3/2 | 3/2 | 2/2 | 8/1 | 7/2 | 6/2 | 7/2 | 7/2 | 6/2 | 6/2 | 6/1 | |||
| 4/1 | 7/2 | 7/2 | 1/1 | 5/1 | 1/1 | 7/1 | 8/1 | 8/2 | 1/2 | 1/1 | 4/2 | 3/2 | 4/1 | 1/2 | 4/1 | |||
| 9/1 | 1/2 | 6/2 | 3/1 | 9/1 | 2/1 | 1/1 | 4/1 | 6/2 | 5/1 | 3/2 | 2/1 | 2/1 | 1/2 | 6/1 | 6/2 | |||
| 3/1 | 3/2 | 3/2 | 5/2 | 3/1 | 1/2 | 8/2 | 3/1 | 3/2 | 7/2 | 6/2 | 7/2 | 7/2 | 6/2 | 6/2 | 6/1 | |||
| 6/1 | 7/1 | 7/2 | 6/2 | 7/1 | 6/2 | 7/2 | 4/1 | 4/1 | 1/2 | 1/1 | 4/2 | 3/2 | 4/1 | 1/2 | 4/1 | |||
| 3/2 | 6/2 | 3/1 | 2/1 | 3/2 | 9/1 | 2/1 | 3/2 | 4/2 | 5/1 | 3/2 | 2/1 | 2/1 | 1/2 | 6/1 | 6/2 | |||
| 6/1 | 6/2 | 1/2 | 5/2 | 6/1 | 6/2 | 8/2 | 6/1 | 6/2 | 6/2 | 6/2 | 4/2 | 6/1 | 4/2 | 6/2 | 4/2 | |||
| 3/1 | 7/1 | 3/2 | 3/2 | 7/1 | 7/2 | 7/2 | 4/1 | 4/1 | 7/1 | 5/1 | 7/2 | 7/1 | 5/2 | 5/2 | 3/2 | |||
| 6/2 | 6/2 | 9/1 | 2/1 | 6/2 | 6/1 | 2/1 | 6/2 | 4/2 | 5/2 | 3/2 | 2/1 | 6/2 | 1/1 | 6/1 | 2/1 | |||
| 3/2 | 7/1 | 8/1 | 2/2 | 9/2 | 3/2 | 3/3 | 3/2 | 7/1 | 7/2 | 4/2 | 4/2 | 1/1 | 4/2 | 4/2 | 3/1 | |||
| 4/1 | 8/2 | 8/2 | 1/1 | 5/1 | 1/1 | 7/1 | 8/1 | 7/2 | 1/1 | 2/1 | 6/1 | 5/2 | 6/1 | 3/1 | 1/2 | |||
| 9/1 | 1/2 | 6/2 | 3/1 | 9/1 | 2/1 | 4/1 | 1/1 | 6/2 | 2/1 | 7/1 | 2/1 | 2/2 | 2/1 | 2/1 | 2/2 | |||
| 3/1 | 3/2 | 3/2 | 5/2 | 3/1 | 8/2 | 1/2 | 3/1 | 3/2 | 7/2 | 2/2 | 7/2 | 7/2 | 2/2 | 2/2 | 2/1 | |||
| 7/1 | 6/1 | 6/2 | 7/2 | 6/1 | 6/2 | 7/2 | 4/1 | 4/1 | 1/2 | 1/2 | 4/2 | 3/2 | 3/1 | 1/1 | 3/1 | |||
| 3/2 | 7/2 | 3/1 | 2/1 | 3/2 | 2/1 | 9/1 | 3/2 | 4/2 | 5/1 | 2/1 | 6/1 | 6/1 | 1/2 | 4/2 | 2/2 | |||
| 8/2 | 3/1 | 2/2 | 2/2 | 8/2 | 8/2 | 9/2 | 5/1 | 3/1 | 7/2 | 4/2 | 4/2 | 1/1 | 4/2 | 4/2 | 3/1 | |||
| 4/1 | 5/2 | 3/1 | 1/1 | 5/1 | 1/1 | 7/1 | 5/2 | 3/2 | 1/1 | 2/1 | 6/1 | 5/2 | 6/1 | 3/1 | 1/2 | |||
| 9/1 | 1/2 | 4/1 | 8/1 | 1/1 | 2/1 | 9/1 | 6/2 | 6/2 | 2/1 | 7/1 | 2/1 | 2/2 | 2/1 | 2/1 | 2/2 | |||
| 1/2 | 1/2 | 1/1 | 5/2 | 1/1 | 8/2 | 3/2 | 1/1 | 1/2 | 5/2 | 2/2 | 5/2 | 5/2 | 2/1 | 2/2 | 2/2 | |||
| 6/2 | 6/1 | 7/1 | 7/2 | 6/1 | 6/2 | 7/2 | 4/1 | 4/1 | 1/2 | 1/2 | 4/2 | 3/2 | 4/1 | 1/1 | 4/1 | |||
| 1/1 | 7/2 | 1/2 | 2/1 | 1/2 | 2/1 | 9/1 | 1/2 | 4/2 | 7/1 | 2/1 | 6/1 | 6/1 | 2/2 | 3/2 | 1/2 | |||
| 6/2 | 4/2 | 5/2 | 4/2 | 4/1 | 4/1 | 8/2 | 4/1 | 4/2 | 5/2 | 6/2 | 5/2 | 5/2 | 6/1 | 6/2 | 6/2 | |||
| 1/2 | 7/1 | 1/2 | 7/2 | 7/1 | 1/1 | 7/2 | 3/1 | 3/1 | 3/2 | 4/1 | 1/2 | 4/2 | 1/1 | 4/2 | 1/1 | |||
| 9/1 | 1/2 | 2/1 | 4/1 | 4/2 | 4/2 | 2/1 | 4/2 | 3/2 | 2/1 | 3/2 | 2/1 | 7/1 | 6/2 | 6/1 | 4/2 |
|
|
|
|
|
|
|
|
Дата добавления: 2015-06-04; Просмотров: 1170; Нарушение авторских прав?; Мы поможем в написании вашей работы!