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