Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 65
Текст из файла (страница 65)
е. представления автомата как структуры, состоящей из объектов фиксированной сложности (элементов). Помимо важного прикладного значения таких задач для проектирования цифровых схем, нх исследование стало, быть может, наиболее существенным вкладом теории автоматов в дискретную математику, поскольку в его ходе впервые было введено и подробно изучено понятие сложности. Это понятие, возникнув как обобщение естественной характеристики цифровой схемы — числа ее элементов, постепенно становится одним из центральных понятий теории алгоритмов вообще; многие количественные характеристики алгоритма, — память, быстродействие, объем собственного описания (программы)— являются различными аспектами его сложности.
В этом отношении теория автоматов оказалась наиболее продвинутой ветвью теории алгоритмов. Заканчивая разговор о проблематике и интерпретациях теории автоматов, упомянем еще об одной интерпретации автоматов, которой объем данной книги не позволит коснуться.
Фон Нейман рассматривал автоматы как удобный язык для описания основных законов взаимодействия сложных систем, т. е. по существу как метаязык кибернетики. Этот взгляд на автоматы как на язык, т. е. концептуальное средство (основу некоторой системы понятий), был подробно разработан М. Л. Цетлиным и его учениками при исследовании задач целесообразного поведения взаимодействующих объектов, которые формулировались как задачи коллективного поведения автоматов.
Очевидно, что содержательный интерес таких задач вовсе не во взаимодействии цифровых схем, а в поведении любых объектов (быть может, живых. существ), возможности которых описаны в терминах конечных автоматов. Подробнее с этими концепциями можно ознакомиться по [8, 19). 312. 33Е РАСПОЗНАВАНИЕ МНОЖЕСТВ АВТОМАТАМИ Автоматы Мура. Конечный автомат называется автоматом Мура, если его функция выходов зависит только от состояний, т.е. для любых д, аь а; Х(д, а;) =Х(д, а~).
Функцию выходов автомата Мура естественно считать одноаргументной функцией; обычно ее обозначают буквой р и называют функцией отметок (так как она каждому состоянию однозначно ставит в соответствие отметку — выход). В графе автомата Мура выход пишется не на ребрах, а при вершине. Общая модель конечного автомата, которая рассматривалась ранее, называется автоматом Мили. Несмотря на то, что автомат Мура — частный случай автомата Мили, возможности этих двух видов автоматов совпадают. Теорема 8А. Для любого автомата Мили существует эквивалентный ему автомат Мура. Пусть дан автомат мили 5=(А, Я, У, 6, Х), А=(аь.., ..., а ), Я=(дь ..., д„). Определим автомат Мура 5~ следующим образом: А„=А, У =)г, Я„содержит гип+и со. стояний: тп состояний д;,(1=1, ..., и; 1=1, ..., т), соответствующих парам (дь а,) автомата 5, и и состояний д о(1= =1, ..., и).
Функции б„и и определяются так: бм(ФИ аь) = =дм„для 1=1, ..., п 6„(йчь аь) =да, где 1 таково, что 6(д„ аь)=~; р(дм) не определено; для остальных состояний р(4О) =ХИ и~) ° Для доказательства теоремы достаточно показать, что для любого йч и любого а 5(дь а) =5 (да, а). Это делается индукцией по длине а; проведение индукции предоставляется читателю. П Рекомендуем в качестве примера построить автомат Мура, эквивалентный автомату Мили из примера 8.1.
Из этой теоремы следует, что при исследовании возможностей автоматов достаточно пользоваться автоматами Мура. Это удобно потому, что автомат Мура можно рассматривать как автомат без выходов, состояния которого различным образом отмечены. Без потери общности можно считать, что этих отметок всего две (например, О и !)„ и они делят состояния па два класса. Зафиксируем один из этих классов и будем называть его состояния заключительными. Это приводит еще к одному определению автомата — автомата без выходов 5=(А, 9, 6, дь г), где Рс:— ыЯ вЂ” множество заключительных состояний. В дальнейшем до конца параграфа будут без специальных оговорок 313 рассматриваться инициальные автоматы без выходов 5 с начальным состоянием дь Представление событий в автоматах.
Множество слов во входном алфавите называется собыгиел. Этот термин стал традиционным в теории автоматов, хотя и необязателен: можно было обойтись просто «множеством слов», Дру. гой термин для множества слов, пришедший из теории грамматик,— «язык» (см. гл. 7). Событие Ея.-А" представимо в автомате 5= (А, Я, 6, 7ь Р), если 6(дь а) «на тогда и только тогда, когда аеиЕ.
Всякому автомату (при фиксированных д, и Р) однозначно соответствует представимое в нем событие; на графе автомата это событие изображается множеством всех путей, ведущих из д~ в вершины из Р. Событие называется представимым (в конечном автомате), если существует конечный автомат, в котором оно представимо. Другие названия этого понятия — множество, определимое, или допускаемое [62), или распознаваемое конечным автоматом. Все эти термины также не обязательны, поскольку п р е д с т а в и м о е в а в т о м а т е событие — это конечно-автоматный аналог разреши мого м нож ест в а; событие Е, представимое в автомате 5, можно было бы назвать множеством, разрешимым автоматом 5.
Может оказаться, что д~«=Р. В этом случае автомат, еще ничего не получив на входе, уже «что-то представляет». Удобно считать, что это «что-то» вЂ” пустое слово (слово нулевой длины); оно содержится в событии, представимом таким автоматом. Пустое слово, как и в гл. 7, будем обозначать е. Для любого слова а еа=ае=а; таким образом, в свободной полугруппе (см. гл. 2) слов входного алфавита, где умножением является приписывание слов друг к другу, е играет роль единицы.
Пустое слово не следует путать с пустым событием, т.е. с пустым множеством (см. аналогичное замечание в гл. 7 в связи с операциями над языками). Автомат представляет пустое событие, если ни одно нз его заключительных состояний не достижимо из начального состояния. Пример 8.6. а. Любое конечное множество слов Е= (аь ..., о») представимо в автомате.
Идея построения автомата по конечному множеству слов иллюстрируется графом на рис. 8А,а, где заключительные состояния д„», ... ..., д, ~ изображены двойным кружком.. Для конкретных множеств эта идея модифицируется в связи с тем, что слова могут иметь общие начала (тогда начала соответствую- 314 щих путей нужно объединить, чтобы не нарушить условие автоматностн) либо просто содержаться друг в друге (тогда из одного заключительного состояния имеется путь и другое заключительное состояние). Пример автомата для Йк г ~хи ~. Риа а.4 Е=(аЬ, ас, аЬаа) с заключительными состояниями Р= =(3, 5, 6) приведен на рис.
8.4, б. В автомате, представляющем конечное множество слов, путь из начального состояния в любое заключительное состояние не может содержать циклов или содержаться в цикле, так как тогда имелось бы бесконечное множество путей из начального состояния в' г" и соответствующее событие было бы-бесконечным. Поэтому такой автомат не может быть сильно связным, он является устройством, так сказать, одноразового действия. б. Автономные автоматы представляют события в од- а,б побуквенном алфавите; слова в таких событиях отличаются только длиной.
Например, автомат из примера 8.3 с начальным состоянием 1 и Р=(7) (выходы опускаем) представляет бесконечное событие, состоящее из всех слов, длины которых при делении па 4 дают в остатке 3. Если же положить Р=(2), то этот автомат представляет пустое событие.
в. Автомат, граф которого приведен на рис. 8.5 (Р= =(1)), представляет бесконечное множество (е, аЬа, аЬааЬа, ..., (аЬа)"...). 3!в События — это множества конечных слов. Однако можно говорить, что автомат распознает бесконечную последовательность букв а=аьаьаь ..., если оп представляет множество Е=(аь, аьаь„..), состоящее из всех начальных отрезков последовательности а. Тео е орема 8.5. Существуют события, непредставимые в конечных автоматах; более конкретно: никакая непериодическая бесконечная последовательность не распознаваема конечным автоматом. Первая половина теоремы после гл.б должна быть очевидной: во-первых, из мощностных соображений (множество событий несчетно, множество автоматов счетно), вовторых, просто потому, что существуют неразрешимые множества.
Поэтому интересно было бы получить пример множества, которое разрешимо (например, машиной Тьюринга), но непредставимо конечным автоматом. Существование такого примера утверждается второй половиной теоремы (пример эффективно заданной непериодической последовательности в алфавите (О,1): 010110111011110...). П ' усть непериодическая последовательность а=аь, аь распознаваема автоматом 5 с и состояниями.
Тогда для любого ее начального отрезка ан...а~ 6(дь ап- ае) =Чь и- ай — Ч0, где ао — заключительное состояние; поэтому при переработке этой последовательности автомат проходит последовательность заключительных состояний а ...а ... Так как и- 0 Щ конечно, то некоторое состояние встретится в этой последовательности дважды: Ей = д, +ь и, следовательно, 6(. а. (а... ап+„..., ан „) =д.п причем все состояния, проходимые автоматом, заключительные. Поэтому, если на вход автомата в состоянии а~ подавать бесконечную периодическУю последовательность а~ = а„...а;, (ай+1. а~ььь) где в скобки взят ее период, то автомат будет проходить последовательность заключительных состояний.
Следова. тельно, все начальные отрезки а~ входят в событие, пред. ставимое автоматом, т. е. автомат не отличает а~ от а и, значит, не распознает а вопреки предположению. П Из теоремы 8.5 следует, что класс множеств, представимых конечными автоматами, является лишь частью (собственным подклассом) класса разрешимых множеств. В свою очередь, из этого обстоятельства и теоремы Райса (э 5А) вытекает, что свойство множества «быть представимым в конечном автоматеэ алгоритмически неразрешимо. Более точно это утверждение формулируется так.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
