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