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