dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 41
Текст из файла (страница 41)
178ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂтолько одному блоку. Состояния из одного блока эквивалентны, а любые состояния, выбранные из разных блоков, не эквивалентны. Теперь можно кратко сформулировать алгоритм минимизации ДКА A = (Q, Σ, δ, q0, F).1.Для выявления всех пар эквивалентных состояний применяем алгоритм заполнениятаблицы.2.Разбиваем множество состояний Q на блоки взаимно эквивалентных состояний спомощью описанного выше метода.3.Строим ДКА B с минимальным числом состояний, используя в качестве его состояний полученные блоки. Пусть γ — функция переходов автомата B. Предположим,что S — множество эквивалентных состояний автомата A, a — входной символ.
Тогда должен существовать один блок состояний T, содержащий γ(q, a) для всех состояний q из S. Если это не так, то входной символ a переводит два состояния p и qиз S в состояния, принадлежащие разным блокам согласно теореме 4.24. Из этогоможно сделать вывод, что состояния p и q не были эквивалентными и не могливместе принадлежать S. В результате определяется функция переходов γ(S, a) = T.Кроме того:а) начальным состоянием ДКА B является блок, содержащий начальное состояние автомата A;б) множеством допускающих состояний автомата B является множество блоков, содержащих допускающие состояния ДКА A.
Заметим, что если односостояние в блоке является допускающим, то все остальные состояния этогоблока также должны быть допускающими. Причина в том, что любое допускающее состояние отличимо от любого недопускающего, поэтому допускающее и недопускающее состояния не могут принадлежать одному блокуэквивалентных состояний.Пример 4.25. Минимизируем ДКА, представленный на рис. 4.8. В примере 4.22 установлены блоки разбиения состояний. На рис. 4.12 изображен ДКА с минимальным числом состояний. Пять состояний этого автомата соответствуют пяти блокам эквивалентных состояний автомата на рис.
4.8.Начальным состоянием минимизированного автомата является {A, E}, так как A былоначальным на рис. 4.8. Единственным допускающим — {C}, поскольку C — это единственное допускающее состояние на рис. 4.8. Заметим, что переходы на рис. 4.12 правильно отражают переходы на рис. 4.8. Например, на рис. 4.12 есть переход из {A, E} в{B, H} по символу 0. Это очевидно, так как A на рис. 4.8 переходит в B при чтении 0, аE — в H. Аналогично, при чтении 1 {A, E} переходит в {D, F}.
По рис. 4.8 легко увидеть,что оба состояния A и E переходят в F по 1, так что для {A, E} состояние-преемник по 1также выбрано правильно. Тот факт, что ни A, ни E не переходят в D по 1, неважен. Читатель может проверить, что и все остальные переходы изображены правильно. 4.4. ÝÊÂÈÂÀËÅÍÒÍÎÑÒÜ È ÌÈÍÈÌÈÇÀÖÈß ÀÂÒÎÌÀÒÎÂСтр. 179179НачалоGD FB HCA EРис. 4.12. ДКА с минимальным числом состояний, эквивалентныйавтомату, изображенному на рис.
4.84.4.4. Ïî÷åìó ìèíèìèçèðîâàííûé ÄÊÀ íåâîçìîæíî óëó÷øèòüПредположим, что задан ДКА A, и мы минимизируем его до ДКА M с помощью метода разбиения из теоремы 4.24. Эта теорема показывает, что невозможно получить эквивалентный ДКА, группируя состояния автомата A в еще меньшее число групп. Но всеже, может ли существовать другой ДКА N, не связанный с A, который допускал бы тотже язык, что и автоматы A и M, но имел бы состояний меньше, чем автомат M? Методомот противного докажем, что такого автомата не существует.Сначала применим алгоритм различимости состояний из раздела 4.4.1 к состояниямавтоматов M и N так, как если бы это был один автомат.
Можно предположить, что общих обозначений состояний у M и N нет, так что функция переходов комбинированногоавтомата будет объединением функций переходов автоматов M и N, которые между собой не пересекаются. Состояния комбинированного ДКА будут допускающими тогда итолько тогда, когда они являются допускающими в соответствующих им автоматах.Начальные состояния автоматов M и N неразличимы, так как L(M) = L(N).
Далее,если состояния {p, q} неразличимы, то для любого входного символа их преемникитакже неразличимы. Если бы преемников можно было различить, то p и q также можно было различить.Ìèíèìèçàöèÿ ñîñòîÿíèé ÍÊÀМожет показаться, что метод разбиения состояний, минимизирующий ДКА, применим и для построения НКА с минимальным числом состояний, эквивалентного данному НКА или ДКА.
Хотя методом полного перебора можно найти НКА с наименьшим количеством состояний, допускающий данный язык, просто сгруппировать состояния некоторого заданного НКА для этого языка нельзя.180Стр. 180ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂПример приведен на рис. 4.13. Никакие из трех состояний не являются эквивалентными.Очевидно, что допускающее состояние B отличается от недопускающих состояний A и C.Состояния A и C различаются входным символом 0.
C переходит в {A} (недопускающее),тогда как A переходит в {A, B}, которое включает допускающее состояние. Таким образом, группирование состояний не уменьшает количества состояний на рис. 4.13.Однако можно построить меньший НКА для этого же языка, просто удалив состояниеC. Заметим, что A и B (без C) допускают все цепочки, которые заканчиваются нулем,а добавление C не позволяет допускать другие цепочки.НачалоРис. 4.13.
НКА, который невозможно минимизировать с помощью эквивалентности состоянийНи M, ни N не могут иметь недостижимых состояний, иначе, исключив это состояние,можно было бы получить еще меньший ДКА для того же языка. Следовательно, каждое состояние автомата M неотличимо хотя бы от одного состояния автомата N. Выясним, почемуэто так. Пусть p — состояние автомата M. Тогда существует цепочка a1a2…ak, переводящая Mиз начального состояния в p. Эта цепочка также переводит N из начального в некоторое состояние q.
Из того, что начальные состояния этих автоматов неразличимы, следует, что состояния-преемники, соответствующие входному символу a1, также неразличимы. Состояния,следующие за этими состояниями при чтении a2, также будут неразличимыми, и так далее,пока мы не придем к заключению, что состояния p и q неразличимы.Поскольку автомат N содержит меньше состояний, чем M, то должны существоватьдва состояния автомата M, которые неотличимы от одного и того же состояния автоматаN. Значит, эти состояния неразличимы. Но автомат M построен таким образом, что всеего состояния отличимы друг от друга.
Противоречие. Следовательно, предположение осуществовании N неверно, и M действительно является ДКА с наименьшим количествомсостояний среди всех ДКА, эквивалентных A. Формально доказана следующая теорема.Теорема 4.26. Если из некоторого ДКА A с помощью алгоритма, описанного в теореме 4.24, построен ДКА M, то M имеет наименьшее число состояний из всех ДКА, эквивалентных A. Можно сформулировать более сильное утверждение, чем теорема 4.26. Между состояниями любого минимального ДКА N и состояниями ДКА M должно существовать взаимно4.4.
ÝÊÂÈÂÀËÅÍÒÍÎÑÒÜ È ÌÈÍÈÌÈÇÀÖÈß ÀÂÒÎÌÀÒÎÂСтр. 181181однозначное соответствие. Как уже доказано, каждое состояние M эквивалентно одномусостоянию N, и ни одно состояние M не может быть эквивалентным двум состояниям N.Аналогично можно доказать, что ни одно состояние N не может быть эквивалентным двумсостояниям M, хотя каждое состояние автомата N должно быть эквивалентно одному из состояний ДКА M. Следовательно, существует только один ДКА с минимальным количеством состояний, эквивалентный A (с точностью до обозначений состояний).4.4.5. Óïðàæíåíèÿ ê ðàçäåëó 4.44.4.1.(∗) На рис.
4.14 представлена таблица переходов некоторого ДКА:а) составьте таблицу различимости для этого автомата;б) постройте эквивалентный ДКА с минимальным числом состояний.→ABC*DEFGH01BADDDGFGACEAFEGDРис. 4.14. ДКА, который нужно минимизироватьВыполните упражнение 4.4.1 для ДКА, представленного на рис. 4.15.→AB*CDE*FGH*I01BCDEFGHIAEFHHIBBCEРис. 4.15.
Еще один ДКА, который нужно минимизировать4.4.3.182Стр. 182(!!) Пусть p и q — пара различимых состояний заданного ДКА A с n состояниями. Какой может быть самая точная верхняя граница длины кратчайшей цепочки, различающей p и q, как функция от n?ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂÐåçþìå♦ Лемма о накачке. Если язык регулярен, то в каждой достаточно длинной цепочке этогоязыка есть непустая подцепочка, которую можно “накачать”, т.е. повторить произвольное число раз; получаемые при этом цепочки будут принадлежать данному языку.Эта лемма используется для доказательства нерегулярности многих языков.♦ Операции, сохраняющие регулярность языков. Существует много операций, результат применения которых к регулярным языкам также является регулярнымязыком.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
