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

*3.1.26. Рассмотрим два МП-прсобразователя, соединенных последовательно, так что выход первого служит входом второго. Покажите, что для такого «тандема» МП-преобразователей мно-жеством всевозможных выходов второго МП-преобразователя может быть любое рекурсивно перечислимое множество.

3.1.27. Покажите, что Г -регулярный перевод тогда и только тогда, когда существует такой линейный КС-язык L, что Т = ~ {(х, у)\хсу L}, где с-новый символ.

*3.1.28. Докажите, что проблема равенства = для регулярных переводов и неразрешима.

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

3.1.29. Разрешима ли проблема эквивалентности для детерминированных конечных преобразователей?

3.1.30. Разрешима ли проблема эквивалентности для детерминированных МП-преобразователей?

Проблема для исследования

3.1.31. Известно, что проблема эквивалентности для недетерминированных конечных преобразователей неразрешима (упр. 3.1.28). Поэтому их нельзя «минимизировать» в том смысле, в котором мы в разд. 3.3.1 минимизировали конечные автоматы. Однако с помощью некоторых приемов можно уменьшить число состояний. Попробуйте найти полезный набор таких приемов. То же самое попытайтесь сделать для МП-преобразователей.

Замечания по литературе

Идея синтаксически управляемин трансляции возникла у многих примерно в одно и то же время. Среди тех, кто первыми стали пропагандировать ее применение, были Айронс (1961) и Барнет и Футрель [1962]. Конечные Преобразователи аналогичны обобщенным последоЬательностным машинам, введенным С. Гинзбургом [1962]. Наши определения СУ-схемы и МП-лре-образователя и результат об их эквивалентности (теорема 3.2) подобны тому что приведено в работе Льюиса и Стирнза [1968]). Гриффите (1968] показал, что проблема эквивалентности для недетерминированных конечных преобпа-зосатстей без е-выходов тоже неразрешима,

3.2. СВОЙСТВА СИНТАКСИЧЕСКИ УПРАВЛЯЕМЫХ ПЕРЕВОДОВ

В этом разделе мы исследуем несколько теоретических свойств синтаксически управляемых переводов и дадим характеристику простых СУ-переводов.

1) Следует также упомянуть работы Чулика [19661 и Петроне [1965] - Прим. перев.

3.2.1. Характеризующие языки

" Определение. Будем говорить, что язык L характеризует перевод Т, если существуют такие два гомоморфизма и П, что r-{(/ii(),

Пример 3.14. Перевод Г {(fl а") Д > 1 [характеризуется языком так как T = {{h,{w), h,(w))\wO-}, где Я, (0) = = /1,(0)-й- □

Будем говорить, что язык L(2uA)* сильно характеризует перевод Г2*хД*, если

(1) SnA-0;

(2) Т\(К{), hAw))\weL}, где

(а) }1{а) = а для всех G и h(b)=e для всех Ь/\ ,

(б) h(a) = e для всех аб и взаимно однозначно отображает Д на Д (т. е. /г -биективное отображение Д в Д).

Пример 3.15. Перевод Г = {(с", Q") п > 1} сильно характеризуется языком Li--{{a"b")\nl}. Он также сильно характеризуется языком L2 = {W\W состоит из одинакового числа C1;M-

волов а и Ь}. Гомоморфизмы в обоих случаях определяются равенствами h(a)a, h,{b) = e и h(a)e, h{b)- а. Язык 0 не сильно характеризует перевод Т. П

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

Лемма 3.4. Пусть T = (N, 2, Д, R, 8)~СУ-схема, в которой каждое правило имеет вид А -аВ, ЬВ или А ->а, Ь, где аи{е}, ЬАи{е} и SN. Тогда т{Т)-регулярный перевод.

Доказательство. Пусть М=-- (N\J {[}, 2, А, б, 5, {!}) - конечный преобразователь, причем f - новый символ. Пусть б (Л, а) содержит (В, Ь), если правило АаВ, ЬВ принадлежит R, и содержит (/, /?), если правило А-а, b принадлежит R. Индукцией по п можно показать, что

(5,x,)t-«(4,e,f/) тогда и только тогда, когда (5, S)=>" (хА, уА)

Отсюда следует, что (S, х, e)\-*[f, е, у) тогда и только тогда, когда (5, 5)=*(х, у). Детали доказательства оставляем в качестве упражнения. Таким образом, т(Г) = т(М). П

Теорема 3.3. Т - регулярный перевод тогда и только тогда, когда Т сильно характеризуется регулярным языком.



Доказательство. Достаточность. Допустим, что L S (2 и Л)* -регулярный язык и и - гомоморфизмы, причем hy{a)--a для дб. hy{a)--e для аД, h{a) = e ]1ля и взаимно однозначно отображает Д на Д. Пусть T{{hy{w), h{w))\w£L}, а G = (N, 2 U Д, -Р, 5)- регулярная грамматика, для которой L (G) = L. Рассмотрим СУ-схему t/=(N, Д, R, S), где R определяется так;

(1) если А-аВ принадлежит Р, то А~->-Ну{а)В, h{a)B принадлежит R\

(2) если А-а принадлежит Я, то A~hy(a), h{a) принадлежит R.

Легко доказать с помощью индукции, что (А, A)ii [х, у) тогда и только тогда, когда А =>oW, {w)x и (w) = у. Отсюда можно заключить, что (S, 5)=Ф(>(х, у) тогда и только тогда, когда (х, у)£Т. Следовательно, x{U) = T. По лемме 3.4 существует конечный преобразователь Л1, для которого т(М)=Т.

Необходимость. Допустим, что Гсг2*хД*-регулярный перевод и M-=(Q, S, Д, 6, £?о, f) - конечный преобразователь, для которого т (М) = Т.

Пусть Д = {а1аЛ} - алфавит, состоящий из новых символов, а G = {Q, iu Д, Р, Qa) - праволинейная грамматика, в которой Р определяется так:

(1) если b{q, а) содержит {г, у), то qah{y)r принадлежит Р, где h-такой гомоморфизм, что h{a) = a для всех аД;

(2) если qF, то q->e принадлежит Р.

Определим гомоморфизмы и равенствами hi (а) -а для всех аХ hy{b) = e для всех b Д h, (а) ~ е для всех а 2 Л) - для всех ЬД

Индукцией по m и по п можно показать, что (q, х, е) [-(/-, у) для некоторого /п тогда и только тогда, когда q="wr для некоторого п, где /г {w)=x и /ig (ау) у. Таким образом, (t?ot )b~"(t?> 1 у) Д*я t? тогда и только тогда, когда £/(, =* wqw, где /г {w) = x и (w)-y. Следовательно, T = {{hy{w), h(w))\w£L(G)) и, значит, L(G) сильно характеризует Т. □

Следствие. Т-регулярный перевод тогда и только тогда, когда Т характеризуется регулярным, языком.

Доказательство. Сильная характеризация-частный случай характеризации. Поэтому в одну сторону («только тогда»)

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

Похоже доказывается аналогичный результат для простых СУ-переводов.

Теорема 3.4, Т - простой СУ-перевод тогда и только тогда, когда он сильно характеризуется КС-языком.

Доказательство. Достаточность. Пусть 7" сильно характеризуется языком, порождаемым грамматикой Gj -(N, S U Д, Р, 5), где 1ц п Ч - соответствующие годгоморфизмы. Построим простую СУ-схему -=(N. 2, Д, R, 5), где R определяется так: для каждого правила А ~а\ВуЮу.. .Bw из Р правило

A~hy (w,) Bji, (Wy). . . Bf,h, (Wf,), h., (w,) B,h., {wJ... Bf,h (Wf,)

принадлежит R.

Индукцией no n легко доказать, что

(1) если Л=> tei, то [А, A)=:zyj.{h,{w), K(w)),

(2) если (Л, А)т{х, у), то существует такая цепочка w, что Л=>£,у и hy{w) = x, h{w) = y.

Таким образом, i{Ty) = T.

Необходимость. Пусть T = i(T), где Т. = (, Z, А, R, S), и Д = \а I а £ А] - алфавит, состоящий из новых символов. Построим КС-грамматику (N, 2иД, Р, S), где Р содер-Ж[1Т правило Л-> XgiBiXi/I. --Вху для каждого правила АхВХ-у. . .Bfx, У>)ВуУ.. .Bfy, принадлежащего R, причем yi получается из у заменой каждого символа йД на сД. Пусть hy и /ig -очевидные гомоморфизмы: hy{a) = a для 02, h(a)e для а£А\ h{a)e для 2 и h{a)a для аА. Снова можно .элементарно доказать индукцией, что

(1) если A=%w, то (Л, A)f{fi,{w), h,(w)),

(2) если (Л, А)т{х, у), то существует такая цепочка w, что Л=Ф£а) и hy{w)---\, h[w)y. п

Следствие. Перевод является простым СУ-переводом тогда и только тогда, когда он характеризуется К.С-языком.. П

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



Пример 3.16. Рассмотрим простую СУ-схему с правилами

5-05, 50

5 -е, е

Покажем, что x{T) = {{w, w)\w{Q, \}*} не является регулярным переводом.

Допустим, что перевод т(Г) регулярен. Тогда найдется регулярный язык />, сильно характеризующий х (Т). Без потери общности можно предположить, что Ls{0, 1, п, Ь\*, а соответствующие гомоморфизмы удовлетворяют условиям h{0) = Q,

Если язык L регулярен, он допускается конечным автоматом MiQ, {О, 1, а, Ь], 6. д„ F)

с S состояниями для некоторого sl. В L должна найтись такая цепочка z, что (г)~0И и h{z)\Q, поскольку (04, £т(Т). Все нули в z предшествуют всем единицам, а вес символы b предшествуют всем символам а. Таким образом, первые S символов цепочки z могут быть только нулями или символами Ь. Состояния, которые пройдет автомат М, прочитав первые S символов цепочки z, не могут все быть разными, так что можно писать z - uvw, причем (9,,, z)]-* (9, vw) f-(<?. h* (Р, где I пу I s. 1I 1 и pF. Тогда avvw L. Но h{uvvw) и h.{uvvw)=\-"0-\ где m и ?г не равны

одновременно нулю. Поэтому (0+"1% 1"0) т (Г). Мы пришли к противоречию, так как предположили, что перевод т(Т) регулярен. □

Пример 3,t7. Рассмотрим СУ-схему Т с правилами 5-..ЛЫ<2>, Л(2Ы<1* A-QA, QA Л->1Л, 1Л

А ~е, е

Здесь t{T){(ucv, vcu)\u, v{OAY*). Покажем, чтот(Г) не является простым СУ-переводом.

Допустим, что -КС-язык, сильно характеризующий перевод х(Т). Можно считать, что Д О, Г, ({О, 1, с U Д)* соответствующие гомоморфизмы. Для любых w, у (О, \ )* найдется такая цепочка z,,.L, что h{Za)ucv и h(z)vcu. Рассмотрим отдельно два случая, связанные с расположением символов с и с в цепочках z.o-

Случай 1: Для каждой цепочки и существует такая цепочка у, что с Предшествует с в г. Пусть -регулярное мно-272

жесгво{0, ЬО, Г}*с{0, 1,0, Г}V {О, 1,0, Г}*. Тогда LR КС-язык, поскольку класс КС-языков замкнут относительно пепесечения с регулярными множествами. Заметим, что множество LViR состоит из тех цепочек языка в которых с предшествует с. Пусть М - конечный преобразователь, который до тех пор, пока не прочтет с, передает на выход нули и единицы, пропуская символы со штрихами. После чтения символа с онне выдает ничего, пока не достигнет с. После этого М печатает на выходе О, прочитав на входе С, и 1 вместо Г, пропуская нули и единицы. Тогда язык M(L{R) должен быть КС-языком, так как класс КС-языков замкнут относительно конечных преобразований, но в данном случае M(LnR) - [ии \ и 6 {О, If*}, а это, как показано в примере 2.41, не КС-язык.

Случай 2: Для некоторой цепочки и не существует ни одной цепочки у, в которой символ с предшествует с в z. Тогда для каждой цепочки v можно найти такую цепочку и, что с предшествует с в 2„j,. Рассуждая, как в случае 1, можно показать, что если бы язык L был контекстно-свободным, то и язык {wy{0, 1}*} был бы тоже контекстно-свободным. Это рассуждение мы оставляем в качестве упражнения.

Итак, перевод т (Г) пе сильно характеризуется никаким КС-языком и, следовательно, ие является простым СУ-переводом. □

Пусть обозначает класс регулярных переводов, <~ класс простых СУ-переводов и- -класс СУ-переводов. Из приведенных выше примеров вытекает, что справедлива следующая теорема.

Теорема 3.5. <r<s<-

Доказательство. - ™ определению, S так как конечный преобразователь -частный случай МП-автомата. Из примеров 3.16 и 3.17 следует, что включения собственные. □

3.2.2. Свойства простых СУ-переводов

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

Теорема 3.6. Пусть Тпростой СУ-перевод. Тогда Т -т: (Т), гое T = {j<i 2, Д, Rf 5) - простая СУ-схема, у которой каждое правило из R имеет один из следующих видов:





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.0019