Главная Промышленная автоматика.

(1) А~ВС,ВС, где Л,В и С - (не обязательно различные) нетерминалы аз N,

(2) Л-у а, Ь, где один из символов а и Ъ есть е, а другой принадлежит 2 или Д соответственно,

(3) 5-е, е, если (е, е)ЕТ, причем. S не встречается в правых частях правил.

Доказательство. Применить конструкцию теоремы 3.4 к грамматике в нормальной форме Хомского. □

Второй результат - аналог теоремы о нормальной форме Грейбах.

Теорема 3.7. Пусть Т-простой СУ-перевод. Тогда Т = г (Гу), где Ty = (N, 2, Д, R, S) -простая СУ-схема, у которой каждое правило из R имеет вид А-аа, Ьа, где aN*, один из символов а и b есть е, а другой принадлежит 2 или Д [с тем же исключением, как в случае (3) предыдущй теоремы).

Доказательство. Применить конструкцию теоремы 3.4 к грамматике в нормальной форме Грейбах. □

Отметим, что в теоремах 3.6 и 3.7 нельзя сделать так, чтобы одновременно было 02 и & А. Тогда перевод сохранял бы длину слова, а для простых СУ-переводов это не всегда так.

3.2.3. Иерархия СУ-переводов

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

Определение. Пусть r = (N, 2, Д, 7?, 5)-СУ-схема. Будем говорить, что Т имеет порядок k, если ни в одном правиле Л->а, р из R цепочка а (а следовательно, и р) не содержит более k вхождений нетерминалов. Будем также говорить, что перевод т(Т) имеет порядок к. Пусть - класс всех СУ-переводов порядка к.

Очевидно, что - - - • • • покажем, что каждое из этих включений собственное, за исключением того, что сз = с2- Дя этого нам понадобится ряд предварительных результатов.

Лемма 3.5. <iа-

Доказательство. Легко показать, что область определения СУ-перевода порядка 1 является линейным КС-языком. По теореме 3.6 каждый простой СУ-перевод имеет порядок 2 и каждый КС-язык служит областью определения некоторого простого СУ-перевода (хотя бы тождественного, для которого этот 3jjj область его определения). Так как линейные языки образуют собственный подкласс КС-языков (упр. 2.6.7), то включение в собственное. □

Для СУ-схем существуют разные нормальные формы. Мы утверждаем, что из СУ-схемы, как и из КС-грамматики, можно устранить бесполезные нетерминалы. Кроме того, для СУ-схем существует нормальная форма, отчасти похожая на нормальную форму Хомского, а именно; все правила можно привести к такому виду, что каждая правая часть либо целиком состоит из нетерминалов, либо не содержит ни одного нетерминала.

Определение. Нетерминал А в СУ-схеме ? = (N, 2, Д,S) называется бесполезным, если либо

(1) нет таких х2* и у€Д*, что [А, А) * [х, у), либо

(2) ни для каких a,,a,(Nu2)* и р,, р, (N U Д)* не существует вывода (5, 5) =>* (ajAttjj, рЛрз).

Лемма 3.6. Каждый СУ-перевод порядка k определяется СУ-схемой порядка k, не содержащей бесполезных нетерминалов.

Доказательство. Упражнение, аналогичное теореме 2.13. □

Лемма 3.7. Каждый СУ-перевод порядка определяется

такой СУ-схемой = (N, 2, Д, 5), что если А-а,р принадлежит R, то либо

(1) а, PN*, либо

(2) «2*, рД*.

Кроме того, Т не содержит бесполезных нетерминалов.

Доказательство. Пусть -(N, 2, Д, 5) -СУ-схема, не Содержащая бесполезных нетерминалов, и т {Т)=Т. Построим R по R следующим образом. Пусть

А -> XoSjXj . . . SftXft, УаСУг . . . Ct/ft

~-Правило из R, причем А > 0. Пусть л-такая перестановка Чисел 1, п, что нетерминал Bj соответствует нетерминалу



Сж/). Введем новые нетерминалы A,D, и Я, Ej,

и заменим это правило правилами

А -Е,А\ Е,А

Efi *" Xfyf Уо

А-Di...Df,, D[.,.Dt, rjxeDi = Da, Для Di-BiE, BEi АЛЯ I ik ул(1) для I</<

Например, если правило имеет вид

А -> х,ВхВхВ,х,, У,Ву,ВуВУз

то JT = (2, 3, 1) и оно заменяется правилами

~> F А

>" Xq f у(у

~BiEi,

BiEi для i

-2» Уз

Xs, у

Так как Di и для каждого / имеют только по одному правилу, легко видеть, что все новые правила в совокупности действуют так же, как правило, которое они заменяют. Правила из R, не содержащие нетерминалов в правых частях, прямо помещаются в R. Обозначим через N множество N вместе с новыми нетерминалами. Тогда х{Т = т(Т) и удовлетворяет условиям леммы. □

Лемма 3.8.

Доказательство. В силу леммы 3.7 достаточно показать, как заменить правило вида А -> ВВВ., CCfis двумя правилами, у которых каждая компонента правой части содержит два нетерминала. Пусть я -перестановка, при которой В соответствует Сю. Таких перестановок может быть шесть. В каждом случае можно ввести новый нетерминал D и заменить интересующее нас правило двумя правилами, как показано на рис. 3.6.

Легко проверить, что в каждом случае новые правила в совокупности действуют так же, как старое. □

Лемма 3.9. Каждый СУ-перевод порядка определяется

СУ-схемой Г=-(1Ч, 2, Д, R, S), удоолетворяюией лемме 3.7 и следующим условиям:

(\) в R нет правила вида А~В, В,

(2) в R fem правил вида А-е,е (за исключением случая AS но тогда символ S не должен встречаться в правых частях правил).

Доказательство. Упражнение, аналогичное теоремам 2.14 и 2.15. □

л (2)

1х(3)

Правила

-BD, BjD D ВВз,

~>-BiD, BD D~BB,

-DBs, DBs D BiBz,

DBs, B<,D D BiB2,

SiD, DBt 0~ВВз,

s2b3

~SiD, DBi D-BBa,

Рис. 3.6. Новые правила.

Теперь определим такое семейство переводов для А 4, что имеет порядок й, но не k - 1, а затем докажем ряд лемм, из которых это будет следовать.

Определение. Пусть й4. Пусть 2 обозначает -только до конца этого раздела - множество {с, Определим пере-

становку для четного к равенствами

если I нечетно

п(1)

если I четно

Например, = (3, 1, 4, 2) и = (4, 1, 5, 2, 6, 3). Определим для нечетного k равенствалш

( - 1

если I = 1

если i четно

если i нечетно н 1ф1

Например, п, = (3, 5, 1,4,2) и л,-(4, 7, 1,6,2, 5,3).

Пусть ГJ - взаимно однозначное отображение, которое переводит

Ример, если а, а, а, а-это а, Ь, с, d, то Т, - {{аЬШу саШ) \ i, j, ft, / > 0}



В дальнейшем будем предполагать, что fe4 - фиксированное целое число и существует СУ-схема Г (N, S,, S, R, S) порядка k-i, определяющая T. Без потери общности можно считать, что Т удовлетворяет лемме 3.9 и, значит, лeшaм 3.6 и 3.7. Мы докажем, получив противоречие, что Т не может существовать.

Определение. Пусть 2 и Л N. (Напомним, что имеется в виду СУ-схема Т, определяющая по предположению перевод Tft.) Множество 2 будем называть (Л, d)-ограниченным в области определения (соответственно в множестве значений), если для каждой пары (х, у), для которой (Л, Л) =>/ (., i/). существует символ а€2, содержащийся не более d раз в х (соответственно в у). Если множество 2 не является (Л, (:?)-ограниченным в области определения (множестве значений) ни для какого d, то будем говорить, что А покрывает 2 в области определения {множестве значений).

Лемма ЗЛО. Если нетерминал А покрывает 2 в области определения, то он покрывает 2 е множестве значений, и обратно.

Доказательство. Допустим, что Л покрывает множество 2 в области определения, но оно (Л, )-ограничено в множестве значений. По лемме 3.6 найдутся такие Wj , w, w, 2, что (5, S)=>* (wAw, WyAw). Пусть m=\ww\. Так как A покрывает 2 в области определения, то найдутся такие ш, wl, что (Л, Л)=>*(ш5, tifi) и любой символ (32 содержится более m-d раз в w. Но так как 2 (Л, г/)-ограничено в множестве значений, то найдется символ /?€2, содержащийся не более d раз в Wg. При этих условиях пара [www, w.jidWj) должна принадлежать Гд, хотя b входит в w. ww. более md раз, а в WjWaW - не более т + 4 раз.

Полученное противоречие показывает, что если нетерминал Л покрывает 2 в области определения, то он покрывает 2 также и в множестве значений. Обратное утверждение доказывается по симметрии. Q

Лемма 3.10 дает право говорить, что А покрывает 2, не упоминая области определения и множества значений.

Лемма 3.11. Пусть А покрывает 2. Тогда суиствуют правило А -> ... В, Су ... Cj„ из Ru такие множества б, ..., в,„, объединение которых совпадает с 2},, что В,, покрывает в,- (lim).

Доказательство. Пусть d - наибольшее нз таких конечных чисел, что для некоторых 2 2i и В,-(1/;т) множество 2 (В., (ц)-ограийчено, но не (В,, - \)-ограничено. Ясно, что такое d существует. Положим dydf(k - 1) + 1, Тогда должны

„яйтнсь такие цепочки х, yl, что (Л, Л)*(х, ) и каяадьш шот a€2ft входит в каждую из них по крайней мере dy раз ?в"пРОтивном случае 2 было бы (Л, <:/,)-ограниченным).

Пусть первый шаг вывода (А,А)->*(х,у) был (Л, Л)=4> (R В , Су ... С,д). Так как по предположению Т имеет пооядок к-и то тк-\. Можно записать х в виде Ху . .. х,„, ппнчем [В,; Bi)=4Xi,yi) для некоторой цепочки у. Для произвольного ak должна найтись хотя бы одиа цепочка х, содержащая а более d раз, потому что в противном случае цепочка х содержала бы а не более d,{k-\)--dy - \ раз. Пусть В/ 2 состоит из символов, которые входят в Xi более d раз. Из предыдущего ясно, что В, U в, U ... ив„ = 2. Тогда 6- для каждого i покрывает в,, так как в противном случае какое-то множество в,- было бы (В,, г/)-огранйченным для некоторого dydf,. Это невозможно в силу нашего выбора числа dfj. □

Определение. Пусть Д/, aj и а, - различные элементы множества 2. Будем говорить, что aj находится между а \\ а, если либо

(1) К! <1, либо

(2) n,{i)<n,{i)<K,{l).

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

Лемма 3.12. Пусть А покрывает 2 и А~Ву...В, Су ... С„ - правило, удовлетворяющее лемме 3.11. Если В покрывает {al и {aJ, а а находится между а,, и а, то В,- покрывает {at} и Bj ни для какого }Ф1 не покрывает {oJ.

Доказательство. Допустим, что г < t < s и Bj покрывает К}, причем 1Ф1. Рассмотрим отдельно случаи /< / и / > (.

Случай 1: j <i. Так как во входной грамматике схемы Т из В,- выводится цепочка, содержащая а, а из Bj выводится 1епочка, содержащая а, то (Л, Л) ~>* (х, ly), где х содержит хождение а, предшествующее вхождению а. Тогда по лемме 3.6 в области определения перевода Т; есть цепочка, которой там

должно быть.

Случай 2: ji. Предположим, что из В/ выводится цепочка, одержащая а. Можно аналогично найти в области определения Рода цепочку, в которой а предшествует а.

юлученное противоречие позволяет исключить возможность

°t что г < / <; S. Единственная оставшаяся возможность -





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 [45] 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0018