Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 62

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 62)

Если все три отображения сюръективны, то эта тройка называется гомоморфизмом 5 на Т, Если, кроме того, зти три отображения взаимно однозначны, то онн называются изоморфизмом 5 на Т; автоматы, для которых существует изоморфнзм, называются изоморфными. Ясно, что мощности соответствующих алфавитов изоморфных автоматов должны быть одинаковыми. Понятие изоморфизма имеет для автоматов тот же смысл, что и для алгебр, рассматривавшихся в гл.

2: автоматы 5 и Т изоморфны, если входы, выходы и состояния 5 можно переименовать так, что таблица переходов автомата 5 превратится в таблицу переходов автомата Т. Изоморфизм графов переходов (без учета букв, написанных на ребрах) является необходимым, но недостаточным условием изоморфизма соответствующих автоматов — см. далее пример 8.4, б. При гомоморфизме, помимо переименования, проис- ходит еще и «склеивание» (например, нескольких состояний автомата 5 в одно состояние автомата Т).

Пример 8.4.а. Возьмем в качестве 5 автономный автомат из примера 8.3, а в качестве 7' — автономный автомат, граф которого приведен на рис. 8.3. Существует гомоморфизм 5 в Т. Соответствующая тройка отображений такова: 1 тривиально, так как оба входных алфавита состоят из Рис. дз одной буквы, а и й зададим списками (для краткости здесь и в аналогичных случаях вместо д,-+.г; будем писать 1-»1); д =(1-+.4, 2-~-3, 3-+-3, 4-+.2, 6-~.1, 6-+.2, 7-+.1, 8-+-6, 9-+7), й = =(О о,1-+«о,2- ~о).

Никакоесостоянне5 не отобразилось в г5, заметим, что г5 недостижимо из других состояний. Это — общее правило: если состояние Т не входит в область значений и при гомоморфизме, то оно должно быть недостижимым для любого состояния из этой области, иначе нарушится условие (8.4). Если из автомата Т состояние г5 вместе с инцидентным ему ребром удалить, то получим новый автомат Т', описанная тройка отображений является гомоморфизмом 5 в Т н 5 на Т'.

Как показывает этот пример, число состояний и выходных букв при гомоморфизме может не сохраняться. Для неавтономных автоматов это же относится и ко входному алфавиту. б. В графе автомата Т рис. 8.3 поменяем местами буквы на двух ребрах: на ребре (гь г2) напишем о, а на ребре (гм г~) напишем в. Получим автомат Т", граф которого изоморфен графу Т; однако сам автомат Т" не изоморфеп Т, Действительно, при изоморфизме графов вершина г4 автомата Т изоморфна вершине г4 автомата Т"; однако Т (г„ ааа) =ооо, Т" (г,, ааа) =оощ, и при любом переименовании выходов в выходном слове Т(гм ааа) все три буквы будут одинаковыми, а в Т" (г4, ааа) — нет.

Пусть 5 и Т вЂ” два автомата с одинаковыми входным н выходным алфавитами. Состоянием автомата 5 и состояние г автомата Т называются неотличимыми, если для любого входного слова а 5(д, а) =Т(г, а). В частности, если Т=5, то речь идет о неотличимых состояниях одного и то- 300 го же автомата 5. Неотличимость состояний д, и д; автомата 5 означает, что инициальвые автоматы (5, д;) и (5, д,) реализуют одно и то же автоматное отображение. Лвтоматы 5 и Т называются неотличимыми, если для любого состояния д автомата 5 найдется неотличимое от него состояние г автомата Т и, наоборот, для любого г из Т найдется неотличимое от него д из 5, Неотличимость автоматов означает, что любое автоматное отображение, реализуемое одним из ннх, может быть реализовано другим; иначе говоря, нх возможности по реализации преобразований входной информации в выходную совпадают.

Отношение неотличимости между состояниями и автоматами, как нетрудно показать, рефлексивно, симметрично и транзитипно и, следовательно, является отношением эквивалентности (см. $ Е4). Обычно неотлнчнмость так и называется эквивалентностью. Терминологически это не очень корректно и удобно: название свойства отношений используется как имя конкретного отношения. Однако в теории автоматов этот термин стал общепринятым, поэтому будем говорить об эквивалентных состояниях или эквивалентных автоматах, имея в виду отношение неотличимости.

Переход от автомата 5 к эквивалентному автомату называется эквивалентным преобразованием автомата 5. Можно ставить различные задачи о поиске автоматов, эквивалентных данному и обладающих заданными свойствами. Наиболее изученной среди таких задач является задача о минимизации числа состояний автомата, нли, короче, о минимизации автомата: среди автоматов, эквивалентных 5, найти автомат с наименьшим числом состояний — минимальный автомат. Теорема 8.2. Для любого автомата 5 существует минимальный автомат 5м единственный с точностью до изоморфизма; если множество состояний 5 разбивается на ( классов эквивалентности (((и): С~=(дц, ..., дп,),...,С~=(~п, ..., да,), то 5о имеет ( состояний.

Если дп и дм — состояния из одного класса эквивалентности Сь то для любой входной буквы а состояния бз(д,ь а) и бэ(дд, а) также находятся в одном классе эквивалентности Сы Действительно, если бз(дд, а) и бэ(дм, а) не эквивалентны, то найдется слово я, такое, что 5(бэ(дп, а), а) М5(бэ(суп,а), а); но тогда в силу (8Л) 5(дп, аа) Ф Ф5(ддь аа), т. е. дп и дм не эквивалентны; что противоречит предположению.

Учитывая это обстоятельство, определим автомат 5а=(Аз, Яз, Уа, 6з„Хз,) так: Яз,= (Сь -. 30! ..., СД; для любого С; и любой входной буквы а бз, (Сь а) = =Сь где Сг — класс эквивалентности, содержащий состояние бз(пт, а) (д» вЂ” состояние из С;; ввиду отмеченного ранее обстоятельства можно взять любое дмыС;); Лз, (Сь а) Лз(дно а). Очевидно, что 5, эквивалентен 5; попутно заметим, что 5о по построению не имеет эквивалентных состояний. Остается показать, что, во-первых, 5з минимален, а во-вторых, любой минимальный автомат 5о изоморфен 5о. Предполо. жим, что 5з не минимален и имеется эквивалентный ему автомат 5," с меньшим числом состояний.

По определению неотличимости для каждого состояния 5я найдется эквивалентное ему состояние 5о, поскольку в 5о меньше состояний, то какие-то два состояния 5з эквивалентны одному состоянию 5; и в силу-транзитнвности окажутся эквивалентными меж-. ду собой, что противоречит отсутствию в 5з эквивалентных состояний. Поэтому5ч минимален. Если же5' — другой минимальный автомат, т. е. имеет то же число состояний, то 5о эквивалентен 5ч и различные состояния автомата 5з эквивалентны различным состояниям 5в, легко проверить, что это соответствие состояний 5ч и 4 является искомым изоморфизмом. П Теорема доказана. Однако, чтобы воспользоваться ею для нахождения минимального автомата, нужно уметь находить классы эквивалентных состояний данного автомата. Само определение неотличимости не содержит метода нахождения, так как оно предполагает перебор по бесконечному множеству входных слов.

Наиболее известным алгоритмом нахождения эквивалентных состояний является алгоритм Мили, который будет описан индуктивно. Пусть дан автомат 5= (А, Я, 'г', 6, Л) с а состояниями. На каждом шаге алгоритма будем строить некоторое разбиение Я на классы, причем разбиение на следующем шаге будет получаться расщеплением некоторых классов предыдущего разбиения. (Отметим, что шаги алгоритма в данном описании вовсе не элементарны. Это скорее блоки.) Шаг 1.

Два состояния д н и' относим в один класс Сп, если и только если для любого аепА Л(д, а) =Л(д', а). Шаг 1+1. Два состояния д н д' из одного класса Сп относим в один класс Сгььь если и только если для любого аыА 6(д, а) н 6(д', а) принадлежат одному и тому же классу Сп. Если (1+1)-й шаг не изменяет разбиения, т, е. состо302 янин из одного класса Сп принадлежат одному классу С,+сь то алгоритм заканчивается и полученное разбиение является разбиением на классы эквивалентных состояний; иначе применяем шаг 1+! к полученному разбиению. Пример 8.5. Для автомата 5 с девятью состояниями и двумя выходными буквами, заданного табл. 8.3, алгоритм строит следующую последовательность разбиений (классы отделены точкой с запятой): 1 4 5 9; 2 3 8; 5 7 1 4 5; 9; 2 3 8; 5 7 1 4; 5; 9; 2 3 8; 5 7 1 4; 5; 9; 2 8; 3; 5 7.

мат описывается табл. 8.4а, в которой снова обозначения состояний (классов С!) заменены их индексами. Обычно, чтобы избежать составления новой таблицы, в исходной таблице оставляют по одному представителю из каждого класса, а строки ос. тальных состояний вычеркивают; в полученной таблице все вхождения этих остальных со- 2,0 1,1 1,1 6,0 6,1 З,О 6,1 4,! 7,0 4,1 1,0 6,0 1,1 4,1 9,1 1,1 4,0 9,1 4,1 6,0 6,0 1,1 З,О 6,1 З,О 7,0 7,1 стояний также заменяют выбранными представителями. В нашем примере вычеркиваются строки 4, 8, 7; в клетках полученной таблицы 4 заменяется на 1, 8 на 2, 7 на 5; в результате получится табл. 8.4, б.

Предоставляем читателю убедиться в изоморфнзме автоматов, заданных двумя табл. 8.4. Поскольку на каждом шаге число классов увеличивается, а общее их число не превосходит п, то описанный алгоритм заканчивается не позднее чем на (а — 1)-м шаге. Докажем теперь, что алгоритм действительно дает разбиение на нлассы эквивалентных состояний. Пусть алгоритм остановился на А-м шаге и а и д' принадлежат одному классу Сы из разбиения, полученного на этом шаге. По условию остановки алгоритма для любого а 5(а, а) и 5(а', а) принадлежат одному классу См! следовательно, это верно для ЗОЗ Последнее разбиение является искомым; минимальный для 5 автомат имеет шесть состояний.

Если найденные классы обозначить по порядку Сь ..., См то минимальный авто- Таблица 8.8 таб И ЗИ ав аа 4,0 4,0 6,0 1,1 1,1 2,1 1,1 з,'! з,! ),о 2,О 1,'! 1,1 2,! 6,1 6,0 6,0 5,*О 2,0 1',1 1,1 6,1 2,0 5,0 1,1 1;о 6,0 1,'1 9,1 9,1 1,1 5,0 5,0 з,'о 6',! 5,1 а) б) (8.6а) «! 6(йп аат) =-6 (6(аь а), а1); 304 любого слова и.

Характеристики

Список файлов книги