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

Алгоритм 2.16. Обнаружение зацикливающих конфигураций.

Вход, ДМП-автомат P = (Q, 2, Г, й, q Z„ F).

Выход. (1) С. -{{q, A)\{q, е, А) - зацикливающая конфигурация и не существует такого rF, что ((?, , Л) j-*(/, а) для некоторой цепочки аГ*} и

(2) СаК, Л)!((?, Л) -зацикливающая конфигурация и ((?, е. А) 1- *(г, е, а) для некоторых г F и аГ*}.

Метод. Пусть 4# q - aij, ф= -длина самой длин-

ной цепочки, которую Р может записать в магазин за один такт. Пусть n - n{ril-n)j[n-\), еслил2>1, и п-п, если п=\. Число - это максимальное число е-тактов, которое Может сделать Я, не зацикливаясь.

(1) Для всех q £Q и Л 6Г выяснить, выполняется ли ((?,(?, Л) 1-"з (г, е, а) для каких-нибудь rQ и аГ+.Прн этом используется прямое моделирование Я. Если да, то {q, е. Л)-зацикливающая конфигурация, так как в этом случае -мы это покажем -должна быть такая пара (q, .Л), гдe(?Q и ЛГ, что

(д,е,Л)1-* (9., ЛР) Н" {q\e,AyP)

где т>0 и у > 0. Заметим, что у может быть е.

(2) Если {q,e,A) - зацикливающая конфигурация, выяснить, существует ли такое г £F, что {q, е. Л) !-(/, а) для некоторого О з. При этом снова используется прямое моделирование. Если да, то включить ((?, Л) в С. В противном случае включить ((?, Л) в Q. Мы утверждаем, что если Я может достичь заключительной конфигурации, исходя из {q, Л), то это должно произойти за или меньшее число тактов. □

Теорема 2.22. Алгоритм 2.16 правильно находит множества Ci и С,.

Доказательство. Сначала докажем, что шаг (1) правильно определяет множество CjUCj. Если (9, Л) g Q и то очевидно, что [q, <?, Л) j-"з(г, е, а). Обратно, допустим, что {q, е, Л)1-"з(г,е, а).

Случай 1: Существует такая цепочка р€Г*» что \р\пп и (д, е, А) j-* [р, в, р) 1-* (г, е, а) для некоторого pQ. Если в

последовательности тактов (q, е, А) [-* {р, е, р) для каждого /=1,2, nnJ--l выделить конфигурацию, в которой оказывается Р, когда длина ого магазина в последний раз становится равной /, то можно заметить, что в выделенной последовательности конфигураций некоторое состояние q и символ Л должны дважды встречаться в качестве текущего состояния и верхнего символа магазина; другими словами, можно писать {q,e,A)[~-{q\e,A6))r-4q,e,Ayd)\-*(p,e,[). Таким образом, по лемме 2.20 [q, е. А)\-* [q, е, Ai-" {q, е, АуЩ яля всех / 0. Здесь тО, поэтому, исходя из конфигурации [q, е. Л), можно сделать бесконечно много -тактов и, следовательно, (9, А)£С\]С-.

Случай 2: Допустим, что в противоположность случаю 1 lllnnj для всех таких р, что {q, е, А)\-* {р, е, р)1-* (г, е, а). Так как в этой последовательности конфигураций имеется --1 различных р, число возможных состояний равно /г и число возможных магазинных цепочек длины, не большей nnl, равно

«а + «2 + + -• «2)/К-1). ТО некоторая

конфигурация должна повторяться. Отсюда непосредственно следует, что (q, A)£C\jC.

Доказательство того, что шаг (2) правильно разбивает множество Ci на Q и Сз, оставляем в качестве упражнения. □

Определение. ДМП-автомат Р - [Q, 2, Г, б, q, Z,, F) назовем дочитывающим, если для каждой цепочки и)2* существуют такие pQ и аГ*, что (q, w, {р, е, а). Интуитивно,

дочитывающим называется ДМП-автомат, способный дочитывать до конца каждую входную цепочку.

Лемма 2.28. Пусть Р {Q, 2, Г, q„ Z, F)-ДМП-автомат. Тогда существует эквивалентный ему дочитывающий ДМП-автомат Р,

Доказательство. В силу леммы 2.27 можно считать, что для Р всегда возможен очередной такт. Пусть Я = (Q U {р, г], 2, Г, 6, qfj, Zq, f и {р}), где р и г - новые состояния, а 6 определяется так:

(1) для всех qQ, aI, к Z £Т положим 6 {q, а, Z) = 6 {q, а, Z);

(2) для всех qQ и Z Г, таких, что, {q, е, Z) не является зацикливающей конфигурацией, положим 6[q, е, Z) - 6 {q, е, Z);

(3) для всех {q,Z)£C-, где С -множество, построенное алгоритмом 2.16, положим 6(9, 6, Z) = (г, Z);

(4) для всех (q, Z)£C, где Cg - множество, построенное алгоритмом 2.16, положим б [q, е, Z)-{p, Z);

(5) для всех аб2 и ZT положим б(/?, а, Z)(r,Z) и д(г,а, Z) = {r,Z).

Таким образом, Р моделирует Я, но если Р попадает в зацикливающую конфигурацию, то Р в очередном такте перейдет в состояние р или г в зависимости от того, встречается или нет в циклической последовательности конфигураций заключительное состояние. Затем, какова бы ни была входная цепочка, Р переходит в состояние г и остается в нем, ничего не меняя в магазине. Отсюда L (Р)== L (Р).

Надо показать, что Р-дочитывающий ДМП-автомат. Правила (3) - (5) гарантируют, что условие „дочитывания" для Я выполняется, если Р попадает в зацикливающую конфигурацию. Остается только заметить, что если Р находится в неза-циклнвающей конфигурации, то через конечное число тактов он должен либо

(1) сделать не е-такт, либо

(2) попасть в конфигурацию, укорачивающую магазин.

Кроме того, ситуация (2) не может повторяться бесконечно, так как в исходной конфигурации магазин имеет конечную длину. Таким образом, либо в конце концов произойдет (1), либо после нескольких повторений (2) Р попадет в зацикливающую конфигурацию. Итак, можно заключить, что ДМП-автомат Р дочитывающий. □

Теперь докажем одно важное свойство ДМП-автоматов, а именно, что класс распознаваемых ими языков замкнут относительно дополнения. В следующем разделе мы увидим, что для класса всех КС-языков это не так.

Теорема 2.23, Если L==L(P) для некоторого ДМИ-сштомата Р, то L - L(P) для некоторого ДЩ\-автомата Я.

Доказательство. По лемме 2.28 можно считать, что Я- дочитывающий. Построим Я так, чтобы он моделировал Я и между сдвигами входной головки выяснял, попал ли Я в допускающее состояние. Так как Ядолжен допускать дополнение языка £(Я), то Р допускает входную цепочку, если Я не допускает ее И собирается сдвинуть свою входную головку (и, следовательно, уже не допустит ее и позже).

Формально пусть P = {Q, S, Г, б, q,, Z„, F) и Р= {Q\ 2. Г, 6, 0. Е) где

(1) l1\qQ. (€{0, 1, 2}},

(2) Я-ЛЯ 0] если q,F, и q = [q,, 1], если qF,

(3) F = {[q, 2]9€Q}.

Состояния вида [9, 0] предназначены для обозначения того, что Я не был в заключительном состоянии после последнего не е-такта. Состояния вида [9, 1] указывают, что в данный момент

Я перешел в заключительное состояние. Состояния вида [q, 2] используются только для обозначения заключительных состояний. Если Р находится в состоянии [9, 0] и в соответствующий момент моделируемый распознаватель Я собирается сделать ие е-такт, то р- сначала переходит в состояние \q, 2], а затем моделирует Я. Таким образом, Р допускает тогда и только тогда, когда Я не допускает. Тот факт, что ДМП-автомат Я - дочитывающий, гарантирует, что и у Р всегда есть шанс допустить входную цепочку, если Я не допускает ее. Формальное определение функции б таково:

(i) если qQy 02 и ZF, то

b{[q, 1], G, Z) = b{[q, 2], а, Z) = ([p, г], у)

где b(q, G, Z)={p, у), i = 0> если pF, и / = 1, если pF;

(ii) если qQ, ZV и 6(9, е, Z) = {p, у), то

Ь{[Я, 1]. Z) = ([/7, 1], у) б([9. 0], е, Z)([/7, il у)

где t=0, если рР, и (=1, если pF\

(iii) если 6(9, е, Z)= 0, то д([q, 0], е, Z) - ([9, 2], Z).

Правило (i) относится к не -тактам. Вторая компонента состояния правильно принимает значение О или 1. Правило (ii) относится к е-тактам, и здесь оно управляется со второй компонентой состояния, как задумано. Правило (iii) позволяет Я допускать входную цепочку в точности тогда, когда Р не до-

пускает ее. Формальное доказательство того, что L(P)-L{P), мы опускаем. □

Детерминированные КС-языки обладают и другими важными свойствами; Мы рассмотрим их в упражнениях и в следующем разделе.

УПРАЖНЕНИЯ

2.5.1. Постройте МП-автоматы, допускающие дополнения (относительно {а, 6}*) следующих языков:

(а) {a"bVnl},

(б) {ww\w{a, }*}*

(в) {а"Ь"а"&« I т, п1},

(г) [ww \w {а, Ь}*}.

Указание: Пусть недетерминированный МП-автомат делает предположение относительно того, почему его входная цепочка не принадлежит данному языку, и проверяет, верно ли это предположение.

2.5.2. Докажите, что МП-автомат из примера 2.31 допускает язык {ww \ w £ {а, b}*}.

2.5.3. Покажите, что каждый КС-язык допускается МП-автоматом, кочорый за один такт увеличивает длину магазина не более чем на единицу.

2.5.4. Покажите, что каждый КС-язык допускается таким МП-автоматом, что если (р, у) € 6 (i/, о., Z), то либо у-=е, либо y = Z, либо y-VZ для некоторого К 6 Г- Указание: Рассмотрите конструкцию леммы 2.21.

2.5.5. Докажите, что каждый КС-язык допускается МП-автоматом, не делающим е-тактов. Указание: Вспомните, что каждый КС-язык порождается грамматикой в нормальной форме Грейбах.

2.5.6. Покажите, что для каждого КС-языка L найдется такой МП-автомат Р с двумя состояниями, что L~L{P).

2.5.7. Дополните доказательство леммы 2.23.

2.5.8. Найдите восходящие и нисходящие распознаватели (МП-автоматы) для следующих грамматик:

(а) S~aSb\e

(б) S-AS\b A~SA\a

(в) S -55Л

Л 0Л1 501

2.5.9. Найдите грамматику, порождающую L(P), где -({9о. 9i. {й. Ь}, {Z,, А], 6, q,, Z„ {qj)

и б задается равенствами

6{q„ а, Z) = {q, AZ,) 6{q„ а, A) = {q,, А А) б(?1, fi, A) = {q„ АА) {Яи е. Л) = ((/„ Л) б((?2, Ь, A) = [q, е)

Указание: Для бесполезных нетерминалов строить правила не обязательно.

*2.5.10. Покажите, что если P---(Q, S, Г, 6, q, Z„ F) - МП-автомат, то множество цепочек, которые могут появиться в его магазине, регулярно. Иначе говоря, покажите, что множество {a\(q, W, Zo)b*(, Л, а) для некоторых q, w я х} регулярно.

2.5.11. Дополните доказательство леммы 2.26.

2.5.12. Пусть Я -МП-автомат, для которого существует такая константа k, что в его магазине всегда не более А символов. Покажите, что L (Р) -регулярное множество.

2.5.13. Постройте ДМП-автоматы, допускающие следующие языки:

(а) {01 <<},

(б) {w\w состоит из равного числа символов а и о},

(в) L(Go), где Go -обычная грамматика, определяющая простые арифметические выражения.

2.5.14. Покажите, что ДМП-автомат из примера 2.36 допускает язык {wcw\w£{a, +

2.5.15. Покажите, что если конструкцию леммы 2.21 применить к расширенному ДМП-автомату, то получится ДМП-автомат.

2.5.16. Докажите, что Я н Я в лемме 2.27 допускают один и тот же язык.

2.5.17. Докажите, что шаг (2) алгоритма 2.16 действительно отличает от С.

2.5.18. Дополните доказательство теоремы 2.23.

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

*2.5.20. Можно еще более расширить класс МП-автоматов, позволив входной головке двигаться по ленте в обе стороны и снабдив входную ленту концевыми маркерами. Назовем такой автомат 2МП-автоматом (двусторонним МП-автоматом), а если он детерминированный, то 2ДМП-автоматом. Покажите, что следующие языки распознаются 2ДМП-автоматами:

(а) {а"Ь«с"п>1},

(б) {ww wk {а, Ь}*},

(в) К" п-\}.

2.5.21. Покажите, что 2МП-автомат может распознать язык {wxw\w, х£ jO, 1}*}.

Открытые проблемы

2.5.22. Существует ли язык, который допускается 2МП-ав-томатом, но не допускается 2ДМП-автоматом?