Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 63
Текст из файла (страница 63)
Но состояния а и д' одного класса заведомо принадлежат одному классу Сц, поэтому Ъ(д, а) = =Ъ(д', а), откуда, учитывая (8 3), получаем, что 5(д, а) = =5(д', а) для любого а, т.е. состояния эквивалентны. Пусть теперь д и д' принадлежат разным классам Сн и С.ы начиная с некоторого г(й. Тогда по построению найдется такое а, что 6(а, а) и 6(а', а) принадлежат разным классам С, ы, С ьб дли них, в свою очеРедь, найдетсЯ такое а", что 6(6(а, а), аа) и 6(6(а', а), а") принадлежат разным классам С,,;, С, к;, продолжив по индукции, получим, что для некоторого слова аллины г 6(а, а) и 6(д', а) принадлежат разным классам Сц, Сц, а это означает, что Ъ(д, а) ~Ъ(су', а) и, следовательно, д и д' не эквивалентны. Частичные автоматы и их минимизация.
Автомат 5 называется частичным, или не полностью определенным автоматом, если хотя бы одна из его двух функций не полностью определена, т.е. для некоторых пар (состояние— вход) значения функций 6 или Ъ не определены. В автоматной таблице неполная определенность автомата выражается в том, что некоторые ее клетки не заполнены— в них стоят прочерки.
В графе частичного автомата в вершинах, где 6 не определена, нарушено условие полноты. Для частичных автоматов определения (8.1) —,(8,3) нуждаются в изменении. При этом будем пользоваться знаком м: запись АакВ означает, что А и В либо одновременно ие определены, либо определены.и равны.
Функция 6(аь сс): а) 6(д» аь) задана таблицей автомата 5; б) если 6 (аь сь) определена, то в) если 6(дь а) не определена, то 6(дн аа~) не определена для всех ап Функция Л(дь а): Л(дн аа;) ==-Л(6(дг а1 а;Л (8.66) Автоматное отображение 5 (дн а): а) 5(дь и;) =Л(дь а,) (если Л(уь а;) не определена, то значение 5(дь а~) считается равным прочерку); б) если 6(оь а) определена, то 5(по аа;) =5(уо а)Л(6(дь а), а7) (8.6) (если Л(6(дь а) а~) не определена, то слово 5(дь ап;) получено из 5(дь а) приписыванием справа прочерка); е) если 6(дь а) не определена, то и 5(дь ааД не определено. Входное слово а, для которого 5(дь а) определено, называется допустимым для д» Из этих определений видно, что функции переходов и выходов неравноправны: если 6 не определена на слове а, то она не определена и на всех его продолжениях; для Л это не обязательно.
Поэтому, если 6 определена на а, а Л не определена на некоторых начальных отрезках а, отображение 5(дь а) «определено, но не совсем»; оно представляет собой слово, содержащее прочерки. Эта ситуация естественно интерпретируется на графе: если 6 не определена на а, то путь а из состояния д~ не определен, поэтому неясно, как его продолжить. Если же путь а из д; определен, то, идя цо нему, можно прочесть и выходное слово 5(дь а); ребрам пути а, на которых не написано выходных букв, соответствуют прочерки в слове 5(дь а).
Понятие неотличимости для частичных автоматов также изменяется, Наиболее простым обобщением обычного понятия неотличимости является следующее. Состояние д~ автомата 5 и состояние г, автомата Т называются псеедонеогличимыми (псевдоэквивалентными), если для любого а 5(дь а)мТ(гп а), т. е. если область определения йч и г~ одна и та же и в этой области д~ и г~ эквивалентны.
Автоматы 5 и Т псевдонеотличимы, если для любого состояния найдется псевдонеотличимое от него состояние Т, и наоборот. Достоинство этого определения в том, что для полностью определенных автоматов оно совпадает с обычным; кроме того, отношение псевдонеотличимости являет. ся отношением эквивалентности. Нетрудно показать, что если прочерк в функции 6 рассматривать как символ 20 — 750 300 нового состояния (переходящего по любому входу только в себя), а в функции Х вЂ” как новую выходную букву, то отношение 5(дь а) ск Т(г;, а) переходит в обычное отношение равенства 5(дь а)=Т(ги а), и, следовательно, применение к частичному автомату 5 изложенного ранее алгоритма Мили даст минимальный автомат, псевдоиеотличимый от 5.
Недостаток зтого определения в том, что оно требует довольно искусственного условия: совпадения областей определения сравниваемых состояний. Позтому понятие псевдо неотличимости оказывается слишком слабым и не учитывает всех возможностей минимизации частичных автоматов.
Поясним на примере, о чем идет речь. Рассмотрим автомат, заданный 3,— 3,0 3,0 2,0 2,1 табл. 8.8. Псевдонеотличимых состояний здесь просто нет. Рассмотрим состояния 2 и 3 (д» и д,), Область определения для дм т.е. для отображения 5(дм а), содержится в области определения для дз; кроме того, на всей области определения д» 5(дм а) =5(дм а) для любого а, так как при любой входной букве Х(дм а) жк(дз, а) и б(д„а) жб(д„а). Можно сказать, что д» «делает больше, чем дг» на тех словах, на которых 5(дм я) определено, а 5(дм а) нет.
Позтому ясно, что если в 5 др заменить на д» (т. е. вычеркнуть строку 2, а переходы из других состояний в д» заменить на переходы в д»), то получим автомат 5', который «делает , больше, чем 5». Это соображение приводит к понятию покрытия для состояний и автоматов. Состояние д~ автомата 5 покрывает состояние г1 автомата Т (5 и Т, возможно, совпадают), если для любого а из того, что 5(гп а) определено, следует, что 5 (дь а) определено и 5 (дь и) =5(г1,а). Автомат 5 покрывает автомат Т, если для любого состояния Т найдется покрывающее его состояние 5.
В частности, состояние, строка которого не содержит прочерков, покрывает все состояния, строки которых получаются из нее заменой некоторых символов прочерками; и обратно, любое состояние д', полученное из состояния д некоторым доопределением, т, е. заменой прочерков символами, покрывает д. В табл. 8.8'0» покрывает дм автомат 5' с двумя состояниями, полученныи заменой д» на дм описанной ранее, покрывает исходный автомат. Отметим, что от- ношение покрытия — это отношение нестрогого (ввиду его рефлекснвностн) порядка; поэтому переход к автомату, покрывающему данный автомат, нельзя называть эквивалентным преобразованием.
Рассмотрим теперь состояния д~ и дэ в табл. 8.8. В отличие от пары дм д, здесь нет оснований считать одно из состояний более сильным, чем другое. Однако эта пара примечательна тем, что можно представить себе состояние, которое покрывает и дь и дв Таким состоянием является состояние, например, со следующей строкой (в табл. 8.8 она получит номер 4): 2,0; 1, —; 3,0, которую можно назвать объединением строк 1 и 2 (можно дать точное определение объединения строк, но надеемся, что оно и так понятно). Это приводит к следующей паре определений.
Состояние д~ автомата 5 и состояние г~ автомата Т вазываются совместимыми, если существует состояние рь (быть может, какого-то третьего автомата )г'), покрывающее и д„ и г» Автоматы 5 и Т совместимы, если существует автомат )г', покрывающий 5 и Т. Совместимости можно дать и более прямое определение: д, и г; совместимы, если для любого и либо одно из отображений 5(д» а), Т(г» а) не определено, либо выходные слова 5(д» я) и Т(г» а) (быть может, содержащие прочерки) непротиворечивы, т. е.
не содержат на одинаковых местах различных букв (например, пара слов в, пэпз — щ и ыэ — — пэ — п~п~ непротиворечива, а пара слов в~ и аз= — и,— п~ противоречива). Понятия покрытия и совместимости дают общий план минимизации частичных автоматов, аналогичный описанному ранее плану минимизации полностью определенных автоматов: находим совместимые состояния и заменяем их покрывающим состоянием (например, объединением соответствующих строк). Однако в реализации этого плана для частичных автоматов есть свои особенности. Дело в том, что отношение совместимости нетранзитивно (например, в табл.
8.8 пары дь дэ и дг, дз совместимы, а пара дь дав нет) и, следовательно, не является отношением эквивалентности, поэтому классы совместимости (т,е. множества попарно совместимых состояний) могут пересекаться. Назовем систему классов совместимости Сь..., С~ полной, если С~()...()С~=Я, и замкнутой, если из того, что состояния д и д' находятся в одном классе С» следует, что состояния 8(д, а) и 8(д', а) также находятся в одном классе С7 всякий раз, когда б(д, а) и 6(д', а) определены.
Теорема 8.3 (теорема Полла — Ангера). Если для час- 307 тичного автомата 5 имеется полная и замкнутая система классов совместимости Сь..., Сь то существует автомат 5', покрывающий 5. Автомат 5'= (Аз. Яз, 'гз, бз, Хз ) строится так: 0з =(Сь...,СД; для любого С; и любой входной буквы и бз (Сь а) =Сь если для некоторых девС; бз(д, а)енС, (классы С~ не могут быть разными для разных д ввиду замкнутости системы классов), и бз (С» а) не определена, если для всех денС; бз(д, а) не определена; ) з (Сь а) :о, если для некоторых д~С; Хз(д, а) =о (буквы о не могут быть разными для разных д ввиду совместимости состояний д из одного класса), и Хз (Сь а) пе определена, если для всех д~С~ Хз(д, а) не определена. Нетрудно видеть, что состояние С, автомата 5' покрывает все состояния из класса совместимости С; автомата 5; следовательно, ввиду полноты системы классов (С;) автомат 5' покрывает 5.
П Эта теорема является аналогом теоремы 8.2 как по содержанию, так и по способу построения искомого автомата; в случае, когда 5 полностью определен, обе теоремы совпадают, Кроме того, алгоритм Мили можно использовать и для минимизации частичного автомата. Для этого нужно сначала построить различные доопределения исходного автомата (ясно, что все они будут покрывать исходный автомат), а затем минимизировать полученные полные автоматы по алгоритму Мили. Однако на этом аналогия с полными автоматами кончается и начинаются собственные — и довольно серьезные — трудности минимизации частичных автоматов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
