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

каждый раз, когда Р делает не е-такт. Р допускает цепочку тогда и только тогда, когда ее допускает Р ц. А находится при этом в заключительном состоянии. Детали доказательства оставляем в качестве упражнения. □

В отличие от регулярных множеств КС-языки не образуют булеву алгебру множеств.

Теорема 2.27. Класс КС-языков не замкнут относительно пересечения и дополнения.

Доказательство. L== {abc /г> 1, /> 1} и = {ab"c I г> 1, д> 1} -КС-языки. Одиако f) L=- {a.b"c" In-line КС-язык (см. пример 2.39), Таким образом, класс КС-языков не замкнут относительно пересечения.

Отсюда можно также заключить, что класс КС-языков не замкнут относительно дополйения. В самом деле, в силу закона де Моргана любой класс языков, замкнутый относительно объединения и дополнения, должен быть замкнут относительно пересечения. Но но следствию т теоремы 2.25 класс КС-языков замкнут относительно объединения. □

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

Пример 2А\. {ww\w£{a, Ь}-} не КС-язык. Допустим, что это не так. Тогда по теореме 2.26 язык L =1ПаЬа-Ь+ = {a"b"a"b\m, п 1} контекстно-свободен. Но в упр. 2.6.3(д) утверждается, что L не КС-язык. □

Пример 2.42. Lr{ww\w£{c, f} + \ не КС-язык. Пусть /г - такой гомоморфизм, что h{c) = a и h {f) = b. Тогда h (L) = {ww w £ {a, &} + } не КС-язык (см. предыдущий пример). Так как класс КС-языков замкнут относительно гомоморфизмов (следствие из теоремы 2.25), то L не КС-язык. □

Пример 2.43. Алгол не является КС-языком. Рассмотрим следующий класс программ Алгола:

L= {begin integer w; ш":-=1; end\w£{c,

Пусть L -множество всех правильных программ Алгола и i? -регулярное множество, обозначаемое регулярным выражением

begin integer (c + f)-; (c4-f)-: = I; end

Тогда L = LaC\R- Наконец, пусть h-такой гомоморфизм, что h(c)=c, h{f) = f и h{X) = e в остальных случаях. Тогда h{L) = {ww\w£ {с,

Следовательно, если L -КС-язык, то /i (L П ) -тоже КС-язык. Однако мы знаем, что язык hiLOR) не контекстно-свободен, и поэтому заключаем, что множество всех правильных программ Алгола не является КС-языком. □

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

В Алголе и многих других языках встречаются и другие явления, характерные для не контекстно-свободных языков. Например, каждая процедура имеет одно и то же число аргументов в каждом месте, где она упоминается. Поэтому можно показать, что подаваемый на вход синтаксического анализатора язык не контекстно-свободен, отобразив множество программ с тремя вызовами одной и той же процедуры на не контекстно-свободный язык {О" ] О" ] О" I /г > 0}. Обычно, однако, для проверки того, что число аргументов процедуры не противоречит ее определению, используется некоторый процесс, не входящий в собственно синтаксический анализ.

2.6.3. Результаты о разрешимости

Мы уже видели, что для КС-грамматик проблема пустоты разрешима. Алгоритм 2.7 получает на входе КС-грамматику G и выясняет, пуст нли нет язык L{G).

Рассмотрим проблему принадлежности для КС-грамматик. Нам надо найти алгоритм, который но данной КС-грамматике (j = {N, S, Р, S) и цепочке к-2* выясняет, принадлежит ли w языку L{G). Получение эффективного алгоритма, решающего эту проблему, внесло бы существенный вклад в содержание гл. 4-7. С чисто теоретической точки зрения можно сразу сказать, что проблема принадлежности для КС-грамМатик разрешима: с помощью преобразований, указанных в разд. 2.4.2, всегда можно превратить G в эквивалентную приведенную КС-грамматику G, а приведенные КС-грамматики (без учета пустой цепочки) контекстно-зависимы, так что можно применить общий грубый алгоритм, решающий-проблему принадлежности (см. упр. 2.1.18).

Рассмотрим проблему эквивалентности для КС-грамматик. i\ сожалению, эта проблема неразрешима. Мы докажем, что не 8*



существует алгоритма, который по двум данным КС-грамматикам Gi и Gz мог бы определить, совпадают ли языки L{Gi) uLiGz)-На самом деле будет доказано, что не существует даже алгоритма, который по КС-грамматике Gj и праволинейной грамматике Gj выяснял бы, выполняется ли равенство L [G) L [G). Как и для большинства других неразрешимых проблем, мы покажем, что если бы проблема эквивалентности для КС-грамматик была разрешима, то была бы разрешима и проблема соответствий Поста. По частному случаю проблемы соответствий мы будем строить два естественно связанных с ним КС-языка.

Определение. Пусть С={х, у), (х„, частный слу-

чай проблемы соответствий над алфавитом 2 и / = {1, 2, ..., п]-, /П2-=0! Положим Lc={Xii.. .x.JJ .. ./Jti, .... inl, т\}яМс-= {У1,У.; yijrnm-i. - -iJ Ч, -.., i„ /, m> 1}.

Лемма 2.29. Пусть C={x, r/i), {x„, у„)~частный случай проблемы соответствий над алфавитом 2, где 2 П {I, 2, ..., п\== 0. Тогда

(1) можно найти расширенные ДЩ\-аетоматы, бопускаюище Сс и Мс,

(2) Lcf)Mc= 0 тогда и только тогда, когда С не имеет решения.

Доказательство. (П Легко построить расширенный ДМП-автомат (верхняя часть его магазина расположена справа), который все входные символы, принадлежащие 2, переносит в магазин, а когда на входе появляются символы из {1,2, ..., «}, он удаляет из магазина х,-, если на входе появилось число i. Если на верху магазина в этот момент не х,-, то ДМП-автомат останавливается. Кроме того, с помощью управляющего устройства с конечной памятью он проверяет, принадлежит ли входная цепочка множеству 2 + {1, п}, и допускает ее, если все символы множества 2 удалены из магазина. Таким образом допускается L. Аналогично можно найти расширенный ДМП-автомат, допускающий УИ-

(2) Если язык Ln Mf-содержит цепочку . .1, где t£e2+, то ясно, что W - решающая последовательность. Если х,-..

У1г--У1т то к/-.-./бсПс- □

Вернемся к проблеме эквивалентности для КС-грамматнк. Нам понадобятся еще два языка, связанные с частным случаем проблемы соответствий.

Определение. Пусть C={Xj, у,), (х,„ (/„) -частный слу-

чай проблемы соответствий над алфавитом 2 и /г},

причем2п/--0- Пололшм Qc= где #2и/

и рЬсФМё-

Лемма 2,30. Пусть С - определенная выше последовательность. Тогда .

(1) можно найти расширенные ЛМЛ-аетоматы, допускающие Qc и Рг,

(2) Qcf)Pc = 0 огда и только тогда, когда С не имеет решения. -

Доказательство. (1) ДМП-автомат, допускающий Q, построить легко. Что касается Р, то в силу леммы 2.29 существует ДМП-автомат, скажем AJj, допускающий L,. Найти ДМП-автомат УИд, допускающий Мс, не намного труднее; он переносит со входа в магазин символы из / и затем сравнивает их с той частью входной цепочки, которая принадлежит 2+. Поэтому можно построить ДМП-автомат М, моделирующий Mj, потом проверяющий, есть ли и, наконец, моделирующий М.

(2) Если uu#wxeQcC\Pc, где и, х1,+ и v, wI + , то и = х и vw, поскольку uv#wxQ. с другой стороны, W - решающая последовательность, так как uv#wxPq. Таким образом, С имеет решение. Обратно, если х.. .х у.. .у, то х,-...

Xijm ...h#h... ixll . . . € Qc П Рс- □

Лемма 2,31. Пусть С-определенная выше последовательность. Тогда

(1) можно найти КС-граммотику для языкаQ[}~P,

(2) QcUPc = {l\ П* погда и только тогда, когда С не имеет решения.

Доказательство. (1) В силу замкнутости класса детерминированных КС-языков относительно дополнения (теорема 2.23) можно иайти ДМП-автоматы для языков и Р. В силу эквивалентности КС-грамматик и МП-автоматов (лемма "2.26) можно найти для этих языков -КС-грамматики. В силу замкнутости класса КС-языков относительно объединения можно Найти КС-грамматику для QcUPc-

(2) Непосредственное следствие леммы 2.30(2) и закона де Моргана. □

Теперь докажем, что проблема, порождают ли две КС-грамматики один и тот же язык, неразрешима. Фактически будет доказано более сильное утверждение: эта проблема неразрешима, даже если одна из грамматик праволинейная.



Теорема 2.28. Не существует алгоритма, который для КС-грамматики и праволинейной грамматики Gg отвечал бы на вопрос: „L (Gi) = L (Gg)?"

Доказательство. Если бы такой алгоритм существовал, то можно было бы следующим образом решать проблему соответствий Поста:

(1) По данному частному случаю С построить КС-грамматику

Gi, порождающую QUP (Тю лемме 2.31), и праволинейную грамматику G, порождающую регулярное множество (2 и/)*. где 2-алфавит последовательности С, /г-еедлинаи/ = {1, .. .,п}. Возможно, придется сначала переименовать некоторые символы, но это не повлияет на наличие или отсутствие решения.

(2) С помощью гипотетического алгоритма получить ответ на вопрос: „L(Gj) = L(Ga)?" По лемме 2.31(2) это равенство выполняется тогда и только тогда, когда С не имеет решения. □

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

2.6.4. Свойства детерминированных КС-языков

Класс детерминированных КС-языков замкнут лишь относительно малого числа нз тех операций, относительно которых замкнут класс всех КС-языков. Мы уже знаем, что класс детерминированных КС-языков замкнут относительно дополнения. Так как L = \abc\i, /1} = {аЫс\ 1, 1}-детерминированные КС-языки, а Lr\L{a"b"c"\n \ } не КС-я5ык (пример 2.39), то отсюда вытекают сразу два свойства незамкнутости:

Теорема 2.29. Класс детерминированных КС-языков не замкнут относительно пересечения и объединения.

Доказательство. Незамкнутость относительно пересечения непосредственно следует из сказанного перед формулировкой теоремы. Незамкнутость относительного объединения следует из закона де Моргана и замкнутости относительно дополнения. □

Приведем пример, показывающий, что детерминированные КС-языки образуют собственный подкласс КС-языков.

Пример 2.44. Легко показать, что дополнение язьжа L = {a*bc I« > 1} - КС-язык. Цепочка w принадлежит L тогда

н ТОЛЬКО тогда, когда выполняются одно или несколькот13 следующих условий:

(1) wa-b+c,

(2) w = abJc и

(3) w = abk я

Множество, удовлетворяющее условию (1), регулярно, каждое из множеств, удовлетворяющих условиям (2) нли (3)-г-КС-язык, в чем легко убедиться, построив распознающие их недетерминированные МП-автоматы. Так как класс КС-языков замкнут относительно объединения, то L -КС-язык.

Но если бы L был детерминированным КС-языком, то по теореме 2.23 и L был бы таким же. Но L даже не КС-язык. □

Для детерминированных КС-языков справедливы те же положительные результаты о разрешимости, что и для КС-языков, т. е. по данному ДМП-автомату Р можно определить, пуст ли язык L{P), я по данной входной цепочке w можно легко определить, принадлежит ли w языку L{P).

Кроме того, по данному детерминированному МП-автомату Р и регулярному множеству R можно определить, совпадают ли множества L{P) и R, так как L{P)=R тогда и только тогда, когда {L{P) П R)\J {L{P) П R) -0. Легко видеть, что язык {L (Р) Г\ R) и {L (Р) г\ R) контекстио-свободен. Другие результаты, касающиеся разрешимости, приведены в упражнениях.

2.6.5. Неодиозиачность

Напомним, что КС-грамматика G-(N, 2, Р, S) неоднозначна, если существует цепочка .w£L{G), имеющая два или более различных деревьев выводов, нли, что эквивалентно, если цепочка W имеет два различных левых или правых вывода.

Если грамматика используется для определения языка программирования, л<елатсльно, чтобы она была однозначной. В противном случае программист и компилятор могут по-разному понять смысл некоторых программ.

Пример 2.45. Самый известный пример неоднозначности в языках программирования-это, по-видимому, „кочующее else". Рассмотрим грамматику G с правилами

S~\fb then 5 else 51 if 6 then S \ a

Эта грамматика неоднозначна, так как- предложение If b then if b then a else a





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