Главная > Разное > Построение и анализ вычислительных алгоритмов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

11.3. ЗАДАЧА, ТРЕБУЮЩАЯ ЭКСПОНЕНЦИАЛЬНЫХ ВРЕМЕНИ И ПАМЯТИ

В разд. 10.6 мы изучили задачу пустоты дополнения для регулярных выражений и показали, что она полна для полиномиальной емкости. Поскольку класс регулярных множеств замкнут относительно пересечения и дополнения, то добавление знаков операций пересечения и дополнения к системе обозначений для регулярных выражений не увеличивает класса множеств, которые можно описать такими выражениями. Однако использование этих знаков сильно сокращает длину выражений, необходимых для описания некоторых регулярных множеств. Из-за возможности такого сокращения для решения ряда задач с расширенными регулярными выражениями требуется еще больше времени, чем для решения задач с "обычными" регулярными выражениями (при условии, что время измеряется как функция длины данного выражения).

Определение. Расширенное регулярное выражение над алфавитом 2 определяется следующим образом.

1. и а из 2 являются расширенными регулярными выражениями, представляющими соответственно пустое множество и

2. Если расширенные регулярные выражения, представляющие соответственно языки то тоже расширенные регулярные выражения, представляющие соответственно языки

Можно в расширенных регулярных выражениях опускать пары скобок, если принять соглашение, что приоритеты операций возрастают в порядке

Далее, знак операции обычно не пишется. Например означает

Если расширенное регулярное выражение не содержит знаков дополнения, то его называют полу расширенным. Задача пустоты дополнения для полурасширенных регулярных выражений состоит в выяснении, пусто ли дополнение множества, представленного данным выражением (или, что эквивалентно, представляет ли все цепочки во входном алфавите). Например, регулярное выражение

представляет множество поскольку

Приступим к доказательству того, что задача пустоты дополнения для полурасширенных регулярных выражений не принадлежит классу значит, не принадлежит классу ибо -ТШЕ содержится в Фактически мы покажем, что существуют такие полурасширенные регулярные выражения длины что решение задачи пустоты дополнения для них требует память (и, следовательно, время) по меньшей мере где некоторые постоянные.

В разд. 11.4 мы увидим, что задача пустоты дополнения для всего класса расширенных регулярных выражений гораздо труднее, чем для полурасширенных выражений. В предвидении этих дальнейших результатов мы будем излагать многие результаты настоящего раздела в терминах всего класса расширенных регулярных выражений.

Кроме сокращений, введенных в разд. 10.6, будем использовать для обозначения расширенного регулярного выражения Мы также будем писать вместо Когда мы будем говорить о длине выражения, то будем подразумевать длину исходного выражения, записанного без этих сокращений.

Теперь введем понятие измерителя. Пусть — алфавит их — произвольная цепочка в . Положим где Пусть специальный маркер, не принадлежащий . Множество называется измерителем с длиной Таким образом, измеритель — это множество всех циклических перестановок цепочки Когда это не будет вызывать недоразумений, мы будем называть измерителем саму цепочку

С помощью измерителя мы будем определять длину МО в правильном вычислении машины Тьюринга. Сначала покажем, как относительно короткими полурасширенными регулярными выражениями можно представить некоторые длинные измерители.

Лемма 11.1. Для каждого существует измеритель с длиной, большей который можно представить таким полу расширенным регулярным выражением что для некоторой постоянной с, не зависящей от

Доказательство. Пусть алфавит из различных символов. Положим для Тогда

Длина цепочки равна 2, а длина цепочки больше удвоенной длины цепочки Поэтому длина цепочки не меньше для

— искомый измеритель. Осталось показать, что некоторое короткое полурасширенное регулярное выражение представляет множество

Для пусть

Положим

и

Мы утверждаем, что полурасширенное регулярное выражение

представляет Для доказательства покажем индукцией по что любая цепочка из множества, представленного выражением имеет вид

где

Базис индукции. Для видно, что представляет в точности цепочки вида

для некоторого Поскольку утверждение верно.

Шаг индукции. Предположим, что представляет все цепочки вида

где

Рассмотрим цепочку из пересечения множества цепочек (11.1) и множества, представленного выражением Каждая подцепочка цепочки принадлежащая и имеющая максимальную длину, должна совпадать с кроме тех случаев, когда она является началом или концом этой цепочки (тогда она равна или Поэтому каждое вхождение можно заменить на (если только оно не в начале и не в конце этого регулярного выражения), не изменяя пересечения множеств (11.1) и Вхождения в начале и конце выражения можно заменить на соответственно. Замечая, что получаем

Наконец, (11.2) можно переписать в виде

где Отсюда вытекает утверждение индукции. Полагая и пересекая с заключаем, что представляет

Осталось показать, что длина расширенного регулярного выражения не превосходит Это непосредственно следует из существования такой постоянной что длина каждого регулярного выражения не превосходит Иными словами, и обозначают расширенные регулярные выражения длины и потому каждое слагаемое суммы, определяющей обозначает расширенное регулярное выражение длины Следовательно, длина полурасширенного регулярного выражения ограничена сверху числом для некоторой новой постоянной с.

Конструкция, аналогичная конструкции из леммы 11.1, позволяет написать короткое регулярное выражение, представляющее множество всех цепочек из кроме Это регулярное выражение понадобится нам вместе с полурасширенным регулярным

выражением только что построенным для представления множества

Лемма 11.2. Пусть алфавит и цепочки те же, что и в лемме 11.1. Тогда найдется регулярное выражение длины представляющее —

Доказательство. Цепочка обладает такими свойствами:

(1) она непуста и начинается с (символы входят в нее парами и за каждым вхождением такой пары идет

(2) для символы также входят парами (в каждой паре два символа отделены друг от друга цепочкой из и за вторым этой пары идет т. е. за символом слева от которого стоят исключительно символы из или непосредственно слева от которого стоит цепочка из имеющая перед собой символ из идет символ

(3) символ входит в точности два раза (за первым вхождением идет а второе является самым правым символом).

Еще важнее то, что единственная цепочка, обладающая этими свойствами. Можно доказать индукцией по что если префикс цепочки, обладающей этими свойствами, то префикс цепочки Например, в силу (1) первым символом является Также в силу (1) изолированный символ не может быть последним в этой цепочке и за ним может идти только следовательно, цепочка начинается с Далее, опять по свойству (1) за должен идти символ В силу свойства (2) при за цепочкой должен идти символ Формальную индукцию оставляем в качестве упражнения. Поскольку на самом деле обладает этими свойствами, эта цепочка и есть единственная, обладающая ими.

Легко написать регулярное выражение, представляющее все цепочки, не обладающие хотя бы одним из этих свойств. Цепочки, не обладающие свойством (1), представляются выражением

Первое слагаемое в обозначает пустую цепочку, второе — те цепочки, которые не начинаются с третье — те цепочки, в которых после пары символов не идет и последнее — те цепочки, которые содержат изолированный символ Цепочки, не

обладающие свойством (2), представляются выражением

Наконец, цепочки, не обладающие свойством (3), представляются выражением

В S первое слагаемое обозначает все цепочки, имеющие более двух вхождений символа а также цепочки с ровно двумя вхождениями символа второе из которых не приходится на правый конец цепочки. Таким образом, представляет Легко видеть, что длина выражения есть

Прежде чем переходить к доказательству отсутствия алгоритма с полиномиальной памятью или с полиномиальным временем работы, который решал бы задачу пустоты дополнения для полурасширенных регулярных выражений, введем два определения.

Определение. Гомоморфизмом из в называется такая функция что для любых цепочек х и у. Отсюда непосредственно следует, что . Таким образом, гомоморфизм однозначно определяется значением для каждого а

Говорят, что гомоморфизм сохраняет длину, если однобуквенное слово из каждого Гомоморфизм, сохраняющий длину, просто переименовывает символы, возможно отождествляя несколько символов путем переименования их в один символ. Если то Если то

Пример 11.2. Пусть Определим гомоморфизм равенствами Тогда Заметим, что не сохраняет длину. Пусть язык, представляемый расширенным регулярным выражением или, в эквивалентной форме, обычным регулярным выражением Тогда представляется расширенным регулярным выражением или обычным регулярным выражением

Лемма 11.3. Пусть сохраняющий длину гомоморфизм из расширенное регулярное выражение, представляющее множество Можно построить такое расширенное регулярное выражение представляющее что его длина будет

Рис. 11.1. Последовательность МО с измерителем.

ограничена длиной выражения умноженной на постоянную (зависящую только от и оно будет содержать знак дополнения только тогда, когда его содержит

Доказательство. Заменим каждое вхождение в символа из регулярным выражением, представляющим множество символов, отображаемых в этот символ гомоморфизмом Например, если множество символов, отображаемых в а, заменим а на Пусть расширенное регулярное выражение, получающееся в результате такой замены. Доказать, что представляет можно индукцией по числу вхождений в знаков

Теперь мы можем представить последовательности МО машин Тьюринга во многом так же, как делали это в лемме 10.2. Иными словами, для данной машины Тьюринга представляем ее мгновенное описание последовательностью символов из и еще одним символом вида где который указывает состояние и положение головки. При необходимости можно дополнить МО пустыми символами, чтобы все МО одного и того же вычисления были одинаковой длины.

Чтобы облегчить сравнение символов одного МО с "соответствующими" символами в следующем МО, приложим к самим МО измеритель, длина которого равна длине этих МО. Формально мы используем "двухдорожечную" цепочку символов, в которой верхняя дорожка содержит последовательность МО, а нижняя — повторяющийся измеритель. Здесь "двухдорожечными" символами служат пары где а — символ на верхней дорожке, на нижней. Это изображено на рис. 11.1, где использован измеритель может быть любой цепочкой, не содержащей

Определение. Для данной положим пусть будет множеством символов, входящих в т. е. множество символов, которые могут появляться на верхней дорожке, а на нижней. "Двухдорожечным" алфавитом будет Правильным вычислением машины с измерителем называют цепочку из множества имеющую вид, как на рис. 11.1, где за один шаг машины для — начальное МО и состоянием последнего является . В МО дописаны пустые символы, чтобы все МО имели длину

Лемма 11.4. Пусть расширенное регулярное выражение для множества регулярное выражение над алфавитом цепочки представляющее все цепочки, кроме х. Можно построить такое расширенное регулярное выражение представляющее все неправильные вычисления машины с измерителем что его длина будет линейной по причем коэффициент пропорциональности будет зависеть только от и оно будет содержать знак дополнения только тогда, когда его содержит или

Доказательство. Цепочка не является правильным вычислением с измерителем тогда и только тогда, когда либо

1) нижняя дорожка не содержится в либо

2) нижняя дорожка содержится в но верхняя дорожка не является правильным вычислением.

Если и алфавиты верхней и нижней дорожек соответственно, то обозначим через гомоморфизмы, отображающие в и соответственно, так что Тогда

представляет те и только те цепочки, у которых нижняя дорожка не принадлежит Первое слагаемое аргумента в представляет цепочки, у которых между двумя знаками стоит нечто, отличное от х, а остальные представляют цепочки, которые не начинаются или не кончаются символом По лемме 11.3 найдется расширенное регулярное выражение с длиной, пропорциональной представляющее это множество.

Данная цепочка удовлетворяет условию 2, когда два символа, отделенные друг от друга символами в количестве, равном длине измерителя, не соответствуют шагу машины либо когда происходит одно или более из следующих нарушений структуры:

1) цепочка на верхней дорожке не начинается или не кончается символом

2) в первом МО или совсем нет состояния, или есть два или более состояний,

3) в первом МО начальное состояние не является компонентой первого символа,

4) допускающее состояние не появляется в качестве компоненты никакого символа,

5) первое МО не имеет корректной длины, т. е. первые два символа на верхней дорожке стоят не в тех же клетках, что и первые два на нижней дорожке.

Покажем, как написать расширенное регулярное выражение для последовательностей в по какой-то причине не отражающих правильные шаги машины Как и в лемме 10.2, замечаем, что в правильном вычислении три последовательных символа на верхней дорожке однозначно определяют символ, стоящий на позиций правее Пусть, как и раньше, этим символом будет Положим

и

Заметим, что представляет все цепочки из которых верхняя дорожка начинается с -все цепочки длины у которых нижняя дорожка корректна. Поэтому их пересечение содержит все цепочки длины которых на нижней дорожке стоит цепочка из а верхняя начинается с Теперь должно быть понятно, что включает все цепочки, удовлетворяющие условию 2, поскольку в них есть шаг, незаконный для Кроме них, туда будут включены некоторые цепочки, у которых на нижней дорожке не стоит они удовлетворяют и условию 1, и их присутствие или отсутствие в несущественно. Далее, длина выражения ограничена длиной выражения умноженной на постоянную (зависящую от Чтобы убедиться в истинности этого утверждения, достаточно заметить, что увеличивает длину регулярных выражений в постоянное число раз, зависящее от Аналогично, увеличивает длину выражений не более чем в раз, ибо если ровно для значений то имеет длину Так как то Более того, должно быть ясно, что поскольку каждый символ из появляется в Следовательно, из (11.3) имеют длину Наконец, очевидно, имеют длину где постоянная зависит только от Поэтому (11.3) и, значит, имеют длину

Регулярные выражения, отражающие упомянутые выше нарушения структуры, строятся весьма просто, и это построение мы оставляем читателю. Изложенным способом можно построить такое расширенное регулярное выражение что его длина будет линейна по и оно будет содержать знак дополнения только тогда, когда его содержит или

Теорема 11.2. Любой алгоритм, выясняющий, представляет ли данное полу расширенное регулярное выражение 1) все цепочки в своем

алфавите, имеет емкостную (и, следовательно, временную) сложность, которая для бесконечно многих не меньше где постоянные.

Доказательство. Пусть произвольный язык с емкостной сложностью но не (Из теоремы 11.1 мы знаем, что такой язык существует.) Пусть допускающая

Предположим, что у нас есть с емкостной сложностью выясняющая, пусто ли дополнение множества, представленного данным полурасширенным регулярным выражением. Тогда можно применить для распознавания языка следующим образом. Пусть входная цепочка длины

1. Построим полурасширенное регулярное выражение для измерителя с длиной или более. По лемме существует и имеет длину Более того, чтобы найти достаточно памяти. Аналогично построим представляющее , где х таково, что . В силу леммы 11.2 выражение имеет длину как легко видеть, его можно построить, заняв клеток памяти.

2. Построим полу расширенное регулярное выражение представляющее все неправильные вычисления машины с измерителем . В силу леммы 11.4 можно построить так, чтобы его длина была не больше где постоянная, зависящая только от

3. Построим регулярное выражение з, представляющее все цепочки из которые не начинаются на верхней дорожке с где начальное состояние машины Очевидно, что существует такое выражение длины Таким образом, для некоторой постоянной

4. Применим М к множеству, представленному чтобы выяснить, пусто ли его дополнение. Если оно непусто, то существует правильное вычисление машины с входом так что принадлежит В противном случае не принадлежит

Можно построить ДМТ М с емкостной сложностью реализующую этот алгоритм распознавания Множитель в аргументе функции появился из-за того, что регулярное выражение над -символьным алфавитом нужно закодировать цепочкой в фиксированном алфавите. Так как мы предположили, что имеет емкостную сложность но не то неравенство

должно выполняться по крайней мере для некоторых Но если бы выполнялось лишь для конечного числа то можно было бы построить модифицированный вариант описанного выше алгоритма распознавания, который сначала проверял бы по конечной таблице, совпадает ли с одним из тех для которых и если да, то узнавал бы из той же таблицы, принадлежит ли языку Поэтому значение должно превосходить для бесконечно многих так что для бесконечно многих и некоторых постоянных

Следствие. Задача эквивалентности полу расширенных регулярных выраокений требует памяти и времени при некоторых постоянных и бесконечно многих

Доказательство. Легко показать, что задача пустоты дополнения полиномиально сводима к задаче эквивалентности, поскольку регулярное выражение, представляющее все цепочки, легко пишется и имеет небольшую длину.

<< Предыдущий параграф Следующий параграф >>
Оглавление