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