1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 95
Текст из файла (страница 95)
Так какмы предположили, что /, имеет емкостную сложность 2", но не 2"/и, то неравенство ') Выбор функции 2" несуществен. Можно было бы вместо 2" взять любую экспоненцяальную функцию Пл), а вместо 2"/л — любую функцию, которая растет чуть медленнее, чем /(п), прн услоанн, что этв функции конструяруемы по памятн. гл. и. иекотогые тРРдио РА3Решимые зхдАчи / (с,п' 1од п))2"/и должно выполняться по крайней мере для некоторых и.
Но если бы /(с,п' !од п))2"/и выполнялось лишь для конечного числа и, то можно было бы построить модифицированный вариант описанного выше алгоритма распознавания, который сначала проверял бы по конечной таблице, совпадает ли !в! с одним нз тех и, для которых /(с,п'!ой и) 2"/и, и если да, то узнавал бы из той же таблицы, принадлежит ли ш языку /.. Поэтому значение /(с,п' !оя и) должно превосходить 2"/и для бесконечно многих и, так что /(т))2"" "я"е "'/~/ т/!ой т)с(с )" "'пяв '" для бесконечно многих т и некоторых постоянных с,= О, с)0 и с')1. П Следствие. Задача эквивалентности пояурасширенных регулярных выражений требует с'с""'Л'е" памяти и времени при некоторых постоянных с')О, с)1 и бесконечно многих п. Д о к а з а т ел ь с т в о.
Легко показать, что задача пустоты дополнения полиномиально сводима к задаче эквивалентности, поскольку регулярное выражение, представляющее все цепочки, легко пишется и имеет небольшую длину. П 1$.4. НЕЭЛЕМЕНТАРНАЯ ЗАДАНА Исследуем весь класс расширенных регулярных выражений. Поскольку теперь у нас есть операция дополнения, достаточно рассматривать задачу пустоты, а именно: пусто ли множество, представленное данным регулярным выражением? Мы увидим, что, располагая операцией дополнения, можно представлять регулярные множества еще более короткими выражениями и задача пустоты для расширенных регулярных выражений значительно труднее задачи пустоты дополнения для полурасширенных регулярных выражений. Определим функцию д(т, и) равенствами 1) а(0, п)=п, 2) й(т, п)=2е'" ""' для т)0.
Тогда а(1, п)=2" д(2, п)=2'" и я(т, и) =2ы' где справа стоит башня из т двоек и последняя возводится в степень и. Функция /(и) называется элементарной, если для некоторого т, она ограничена сверху функцией д(ты и) для всех, кроме конечного числа, значений и. С помощью техники равд. 11.3 можно доказать, что задача пустоты для всего класса расширенных регулярных выражений не может иметь емкостную сложность 5 (и) ни для какой элементарной !ЕЛ НЕЭЛЕМЕНТАРНАЯ ЗАДАЧА Юерхаял ввнмсла Н юлФмяяа Рис. !!.2.
Новая форма правильных вычислений с иамерителем. функции Ю(п). Прежде чем приступить к доказательству, изменим немного определение правильного вычисления машины Тьюринга М=Я, Т, х, 6, Ь, д„в,) с измерителем ЦИКЛ(х4с). Удалим первый маркер 4с и заменим последний маркер новым символом 3 (рис, 11.2). Обозначим через С, МО (дополиенные, если надо, пустыми символами, чтобы их длина стала равной длине цепочки х); как и раньше, С!( — С,+х за один шаг машины М для 0(а~(, С,— начальное МО и С, содержит состояние ае Будем использовать следующие обозначения (предполагаем, что х ~ г'е): 1) ЬЗ=Т 0 (!е'ХТ) 0 (4Ь, 3) — алфавит верхней дорожки, 2) й,=х. 0 (№, й) — алфавит нижней дорожки, 3) Ь;.
Л,ХЬ;Рбн причем й, ((а, Ь))=а, 4) и;! Лаху;РЬ„пРичем Ьа((а, д))=(А Лемма 11.5. Пусть )ех — расширенное регуллрное выражение для множества ЦИКЛ!х4с). Можно построить такое расширенное регулярное выражение Й„представляющее множество циклических перестановок правильных вычислений машины Тьюринга М с измерителем ЦИКЛ(х№), что !Иа~ есть 0(Яй), где постоянная зависит только от М. Д о к а з а те л ь с т в о. Цепочка является циклической перестановкой правильного вычисления с измерителем ЦИКЛ(х№) тогда и только тогда, когда !) нижняя дорожка — циклическая перестановка цепочки вида (х4~) х3, 2) верхняя дорожка — циклическая перестановка правильного вычисления машины М и 3) верхняя и нижняя дорожки циклически переставлены оди- наково. Пусть )с; — это выражение Ян в котором вместо 4ь стоит символ Цепочки, удовлетворяющие условию 1, можно представить выражением й,'(Ух() У~() Уа), где и,=Х (№+3)У,+г;)П(Б 4+Х*Ц*Х, и,=(Б+№) 3(Х+4ь) .
(Уа (хех+ ахь) ° гл. и, нвкотогыа тггдно глзгашимыв злдлчн Подвыражение [(й,+Р;) () (2*4~+2*й)1 в У, представляет две цепочки х4э и хф. Поэтому 1/, представляет Х ь(4э+й) (к4е+ +хЗ)*Е*. Выражение У, содержит цепочки с ровно одним вхождением $. Поэтому всякая цепочка из У, П У, имеет вид у,.я хя х4э...х 1~хйкф...х~у„ где у, н у, — некоторые цепочки из Х". Выражение У, приводвт к тому, что !у,)+~,~=~к~, откуда легко следует, что у,у,=х для цепочек из У,() У,() У,. Таким образом, З,=У,() У,() У, представляет нижнюю дорожку всех цепочек, удовлетворяющих условию 1. Что касается условия 2, то в лемме 11.4 мы видели, как написать полурасширенное регулярное выражение для неправильных вычислений машины М с измерителем ЦИКЛ(х/~).
Зта техника легко переносится на форму, показанную иа рис. !1.2, и мы предлагаем читателю самому построить выражение Е, представляющее циклические перестановки неправильных вычислений машины М с корректным измерителем на нижней дорожке. Применение операции дополнения к Е дает расширенное регулярное выражение 5,. Это единственное место, где применяется дополнение. Должно быть ясно, что все цепочки, представленные выражением 3,() Зм удовлетворяют обоим условиям 1 и 2. Выражение для условия 3 в предположении, что условия 1 и 2 выполнены, строится без особого труда. Надо лишь проверить, что один символ имеет й на обеих дорожках.
Пересекая это выражение с 5~ (1 5м получаем требуемое. (З Теперь покажем, как с помощью леммы 11.5 выражать все более и более длинные измерители, не слишком увеличивая длины задающих их выражений. Интуитивно мы строим регулярное выражение для какого-то измерителя с небольшой длиной, скажем с длиной а. Затем используем его, чтобы построить новое регулярное выражение для всех циклических перестановок правильных вычислений с этим измерителем для некоторой машины Тьюринга, допускающей в точности одну цепочку длины л. Машина Тьюринга специально выбирается так, чтобы на входе длины л она делала по меньшей мере 2"+' шагов, поэтому множество циклических перестановок ее правильных вычислений само будет измерителем с длиной 2" нли более.
Повторяя этот процесс с новым измерителем, получаем измерители все с ббльшими и ббльшими длинами, но не меньшими 2", 2'" и т. д. Пусть М, — конкретная одноленточная машина Тьюринга, которая ведет себя так: 1) проверяет, что ее входная лента начинается с последовательности символов а, для чего просматривает эту ленту до первого пустого символа, 2) если входная лента содержит цепочку из гп символов а, за которыми стоит пустой символ, считает в двоичной системе чс4. неэлементАРНАЯ зАдАчА от () до 2 " — 1 на части своей ленты, которая была занята символами а и следующим за ними пустым символом, 3) досчитав до 2»+' — 1, останавливается и допускает свой вход.
Итак, М, обладает следующими свойствами. Для каждого и она допускает в точности одну цепочку длины п, а именно а". Она делает зто, выполняя единственное правильное вычисление, состоящее не менее чем из 2" +* шагов, поскольку половина ее шагов добавляет биты, а другая половина осуществляет переносы. Наконец, М, просматривает только и+1 клеток ленты, когда ей подан вход длины и. Исследуем теперь правильные вычисления машины М, с измерителем ЦИКЛ(хв(Ь), имеющие вид, показанный на рис.
11.2. Если (х)=п+1, то существует единственное правильное вычисление машины М, с измерителем ЦИКЛ(хор), у которого верхняя дорожка начинается с [о,а!а... а Ьв(Ь. По лемме 11.5 для всех его циклических перестановок можно построить регулярное выражеииеКа. Оно будет представлять множество, состоящее из циклических перестановок фиксированной цепочки шЕ (Л,Хйз)». Цепочка й,(ш) будет правильным вычислением машины М, на входе а", где, напомним, |х!=и+1. Так как М, делает на входе а" не менее 2" ' шагов, Я, можно взять в качестве измерителя с длиной не менее 2»»з Итак„пусть даи измеритель ЦИКЛ(хвв), представленный выражением )го где хЕХ». Тогда по Я, и описанной выше ДМТ М, можно построить измеритель с длиной, не меньшей 2"ац По лемме 11.5 для него найдется регулярное выражение )га длины не более с,()г,~, где постоянная с, зависит только от М,. Лемма !1.6.
Для всех 1~! и т)2 существует измеритель с длиной, не меньшей й(1, т) '), который можно представить расширенным регулярным выражением длины не более с(с,)' 'т', где с,— постоянная, зависящая от М, и введенная в предыдущем абзаце, а с— поспюянная из леммы 11.1. Д о к а з а тел ь с т в о. Докажем индукцией по 1, что найдется расширенное регулярное выражение )г„представляющее ЦИКЛ(хКл) для некоторого х, где !хф-!)д(1, т) и )Я,)(с(с,)4-'та. Базис (1=1) следует из леммы 11.1 при й=т, поскольку можно построить расширенное регулярное выражение длины ст', представляющее ЦИКЛ(хве).
Для шага индукции допустим, что построено расширенное регулярное выражение !г, длины !!с, Кс(с,)' 'т', представляющее ЦИКЛ(хв(Ь), где (хв(ь ~)д (! — 1, т). Тогда на основе проведенного выше анализа, касающегося ДМТ М„заключаем, что можно по- '! Функцня й определена а самом начале раздела. 449 гл ~ и накотогыв тгкдио гьзгашимые зьдлчи строить регулярное выражение Р длины не болеее,Я,~=с(с,)!-'т', представляющее ЦИКЛ(у$), где ~уф)2' «~)2еи-' ""=й(1, т). П Теорема 11.3. Г! усть 5 (и) — любая элементарная функция. Тогда не суи(ествует ДМТ с емкостной (и, следовательно, временной) сложностью, ограниченной сверку функцией 5 (и), которая могла бы установить, пусто ли множество, представленное произвольным расширенным регулярным выражением.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
