1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 10
Текст из файла (страница 10)
гл. 1, 5 1, и. 1А) раэрешимо, но не существует определяющего его конечного одноленточного авто- й» мата. Наглядным способом задания конечных автоматов служат графы автоматов. Автомат А представляется а виде графа, множество вершин которого — множество состояний Ч, и иэ э Ь вершины д в вершину д' ведет дуга, помеченная символом а, тогда н только тогда, когда программа автомата с Сг содержит команду да — д'. Легко видеть, что граф автомата однозначно я описывает автомат. Работе автомата е над заданным словом соответствует путь нэ начальной вершины дм По- л следовательность проходимых вер- рве, ЗА.
Автомат, леяусвэюшнн этого пути — это последова- щай множество слов (а»»Ь"» ~ п = тельность принимаемых автоматом = 4, Э,...; э» = 1, Х,...) состояний, обраэ пути по дугам— читаемое слово. Любой путь в графе автомата, начинающийся в вершине де и заканчивающийся в вершине д Е= В, порождает слово, допускаемое автоматом. Пример конечного одноленточного автомата, допускающего множество слов (а"Ь ~ л = 1, 2,...; ю = 1, 2,...) в алфавите (а, Ь): А = Яа, Ь) фуо да дв»»та) (па]» оо 4~» Г).
Программа 1 (рис. ЗЛ): Ч»а «Ч» Ч»а «Ч» Ч»Ь вЂ” «Ча, ЧЬ Ч„ Ч»а Чвв Чза — «Ч31 Ч,Ь- Ч» Ч,Ь- Ч,. !.2. Проблемы пустоты и эквивалентности. Автомат А называют нуетыл», если Мл = Я. Автоматы А и А эквивалентны, если Мл, = Мл,. Для машин Тьюринга проблемы пустоты и эквивалентности неразрешимы, более того, они не являются частично разрешимммн (см. задание 1.6). Ситуация меняется для конечных автоматов, подтверждением чему служат следующие две теоремы.
Т е о р е м а ЗА (Рабин — Скотт). Проблелш куек»оты конечных одноленточнмх автоматов разрешима. Д о к а з а т е л ъ с т в о. Покажем, что для обнаружения пустоты множества Мл достаточно подать на ленту автомата нзд алфавитом е" некоторое конечное множество Мл слов, а именно все те слова из уч, длина которых меньше числа состоянвй автомата, Если автомат не допускает ни одного нз них, то он пуст. Если же автомат не пуст, то найдется допускаемое елово, длина которого меныпе числа состояний к. Предположим противное: пусть а — минимальное допускаемое слово и его длина т больше или равна н.
Выпишем путь (х, у»..., х» у„..., хв, у»... ..., у, х,») в графе автомата, ведущий из начальной вершины х = Чз в веРшинУ х „= Ч, где Ч б= Л, и соответствУющий Работе автомата над словом сс. Число проходимых вершин этого пути болыпе к. Поэтому найдется пара вхождений вершин в путь х, и хт такаЯ, что х, = хв = Ч', где Ч' С= (). Очевидно, что пУть, полученный из предыдущего удалением участка (у»..., хв), так»ке описывает работу автомата и ему соответствует слово а', которое допускается автоматом, но имеет длину менъшую, чем слово а. Это противоречит предположению, что ы — минимальное допускаемое слово. ~ Т е о р е м а З.2 (Рабин — Скотт).
Проблема эквивалентности конечных однвленточнмх аыпоматов разрешима. Д о к а з а т ел ъ с та о. Без потери общности можем предполод»ить, что автоматы А» и А имеют общий алфавит К Пусть А, — автомат над Г с тем же множеством состояний, что н автомат А» и с определяемым множеством слов Мл — — ез ~~, Мл,. Такой автомат можно построить, заменив множество заключителъных состояний Л, автомата А» на множество Н» = Щ, ~ Л» Аналогично можно определить автомат А,. Автоматы А» и Аз эквивалентны тогда и толъко тогда, когда М ПМ- =8 М„ПМ- =8. Таким образом, чтобы установить эквивалентность автоматов А н Аз, следует проверить, пусты лн одновременно автоматы Аэ и Аз такие, что М =М„<)М- М =М Г)))У Автоматы Аз и Аз можно построить по автоматам Аз, Аз, А и Аз, если допустить использование в качестве состояний не только символы, но и пары символов состояний автоматов Аз и А .
Действительно, автомат Аз имеет следующий вид: Аэ = (Т»» Дз Х (г»з»»гз Х Лз» (Фп»»ззз)»»з)» где доз — начальное состояние автомата Аз; дж — начальное состояние автомата А; г — программа автомата А, содержащая команду (<<з» дз) а- (дз» йз) в том н только том случае, если программа автомата Аз содержит команду д а -»- д н программа автомата А содержит команду дза — ою Аналогично строится автомат Аз. Проблема пустоты конечных одноленточных автоматов разрешима.
Поэтому процедура распознавания эквивалентности автоматов сводится фактически к построению автоматов Аз и Аз и последующему анализу, являются лн оба построенных автомата пустыми. [) Задание ЗЛ А. Постровте однолевточвые эвтомзты кзд алфавитом (а, Ь, с), дспускеющне следующие ююжестэа слов: <х 'ЬЬЬ< > О), <е'сь' < > 1, ю ~ П, << ЬЬ)о< х > 1).
Б. Покзжвте, по множество слсв (а"Ь" ~ х> Ц в алфавите (е, Ь) ве спределвмо вннзквм одиоленточвмм евтонатом. В. Покзжвте, что множество правнльвыг. слов в алфавите ((, )) (см. гл. 1, 1 1, п. 1.4) не определимо ввкекэм однолеаточвым автоматом. Г.
Существует лв алгоритм, которнй для любого автомата л распознает, является лн икон»естес Мл конечным влв бесковечнымг Д, Обое»эххнах фуххэих х»реходох б: О Х у» Ч конечного автомата А = (У, О» В, чь» 1) определяется таким обрезом, что б (т, х) — это то состояние, к которому ведет путь, вачннеющвйся состоянием т к обрезом которого по дугам является слово х.
Более точно, (Э. есле х=е, б(э' ) ~т ° ж» ио, где уж т х г в <Е<т,р)е т')юу. Теням обрезом, Мя — — (х < б (чз, х) ю В). Дэа состояввя тз к Эз назовем ххвиеалххюхнхх, если для всех х зк Ре б (тз, х) ю В еь б (Эз, х) е В. Отиожевве эквнэелентностн двух состоявнй обледяет следующкм вежвмк сэойстэомз еслн состояния т к т' эквивалентны„то для всех е ю У состояния б (т, х) и б (т', а) также эквнвазевтвы. Кроме того, ввнекое эаюпечвтелыюе состоявке не может быть экввзелеатвмм иемзклкжатеэьвому.
Поэтому для респозвззмвкя эквивалентности двух автоматов южщо действовать сведующим обрезом: предположим, что автоматы эквюмлевтвы; тогда зкэиэалекгюе пх начальные состояввя, откуда можно эывестк эквюмлевтность дла другах вар состояний, которые, в свею очередь, влекут эквквелевтвость новмх пэр состоавкй, к т. д. Если в одну вз текил пар попедет еаключателыюе состоякве вместе с вемпопечвтезьвым, то исходные автеметы были неэнвнэелеитинмп. Если же етого нэ произойдет, то исходные автоматы эквнвзлевтны, Опишите подробво алгоритм, реалвэушщай сформулирожжкуш вдеш. Докажете, что ои дейстаителыю распоэвает экаииалеитпость аатоматоз. От- метим, что храпение пар эквиаалеитимх ссстояявй а такам алгоритме мозжи оргавкэоеать так, что время его работы будет саши.н.
С (и), где и — суика количеств состояпий всходвмх аэтаматоа (иад фпкспроаавпмм алфавитом у), а С(и) — очень медленно растущая фуикцпя [1): Р(0)= 1, Г (н) = 2Р»" П для н.э О, С (и) = ппп (д ~ Р (д) : и). Например, С (и) Ч„б дяя всех и ~ 2оии~. Е. Есле Ат = (У, Со Вм йо 1т) и Аэ = (У. Ра. Лэ, Уо, 1 ) — даа автомате иад общем алфааитом У, то автомат А = (у, О х Сэ, в, х лм (т„т,), 1), где программа 1 содержит команду (о, о') и — (ио ч ) тогда к только тогда, когда 1т содержит комапду то то, а программа 1 — иомаиду т'а - чо, яаэмиается ироиооодониом аоомматоо Ат и Аэ с отоиодоотоаониом аэодоо Докажите, что Мл —— Мл П Мад й 2. Многолевточвые автоматы 2.$. Определения. Автоматы, о которых пойдет речь, возникли как попытки обобщения одноленточного, одностороннего, детерминированного автомата за счет усложнения его поведения и увеличения числа лент.
Одноленточные обобщения, такие, как двусторонний автомат, головка которого может перемещаться вправо и влево, и недетерминированный автомат, очередное состояние которого выбирается произвольно нз некоторого множества состояний, оказались не белее мощными, чем рассмотренный выше автомат ИЗЗ). Это значит, что существуют алгоритмы, которые по любому обобщенному автомату строят эквивалентный односторонний детерминированный автомат. Более интересными оказались дмималенточные (детерминированные, односторонние) аетяаматм.
Формальное отличие п-ленточного автомата (и ' - 2) А = (г, ® В, до, 4р, о) от рассмотренного в предыдущем параграфе одноленточного автомата состоит лишь в том, что задано разбиение множества состоянвй () на и непересекающихся подмножеств ф,..., ()„. «Физическая» интерпретация я-леяточного автомата отличается тем, что он имеет и лент и п головок, по головке на ленту. Если автомат находится в состоянии д е= ~), (( «(1~ я), то 1-я головки читает свою ленту точно так же, как зто делает одполенточный автомат. При переходе автомата в состояние д ч= ()1 () Ф 1» 1-я головка останавливается, а 1-я начинает читать свою ленту. Автомат останавливается только в том случае, когда головка на одной нз лент прочитала символ Чр.
. Мы говорам, что набор слов (и,..., и„) над г" переводит автомат в состояние о, если для некоторого т ~ О существует по- 42 следовательиость состояний д», д»,..., д из (у, а также слово лся»... я кад У такие, что (а) Ус 7$ «( с «( ш) (д,',а, — д,) Е Г, (б) дм .= д, (в) УЙ (» ч,:; ус 4; и) и» вЂ” это слово, получаемое последователькым выписываю»ем всех символов ас слова ас...
а,„таких, что д, ~ф,. Автомат А допускает набор слов (и»,..., и„), если 3~(1 ~ с~я) Уу(1«(у ~ и, у ~ с) Зс»н ссу такие, что и, = = ссуссу, а набор слов (ссс,..., а, », и„с»с+»,..., сс„) переводит автомат А в состояние д~ф, для которого (д~- д') с=: 1 я д' е уу. Как и ракьше, МА будет озиачать множество всех набор».в слов, допускаемых автоматом А. Два автомата А» и А» иазываются оквиаменксними, если Мж = Мк,. Приведем пример двухлеиточпого автомата А». = (У, (у () ( ) (у», уу; д, ~, 1), который допускает множество пар лент ((и, и) ~ и = ии' для некоторого слова и') алфавитом У = (О, »). —, Зд д, = (д~, д'.), р, = (дм д'., д*,), уу = (д'), у = (О, ц), ~Я ' качальпое состоякие.
Граф автомата показал иа рис. 3,2. ~' Для описакия алгоритма распозиавакия эквива- 1 Ф '1 леитяости дзухлеиточвых е дс » автоматов мы введем в рассмотрение упрощенную форму мяоголеиточкого ав- д» томата, понятия диаграммы и полудиаграммы. Пусть Е„..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
