Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Покажем, что язык L' не пересекается с множеством D(Z) — D'(Z), Действительно, пусть BeL'fl[i)(Z) —
— D'(Z)]. Поскольку цепочка ю принадлежит D(Z), ее можно сократить до пустой цепочки, последовательно вычеркивая пары вида аа или аа, где asZ. В то же время a^D'(Z); поэтому при сокращении хотя бы один раз должна быть вычеркнута пара вида aa, иначе говоря, о должна содержать подцепочку вида aga, где I сокращается до пустой цепочки. Цепочку | можно выбрать так, чтобы при ее сокращении никакая пара вида РР не вычеркивалась. [Если ? этим свойством не обладает, то она содержит подцепочку PiiP, где ?i сокращается до пустой цепочки; если |i еще не обладает нужным свойством, то она содержит подцепочку такого же вида, и т. д.] Пусть цепочка g такова; она не может быть пустой, поскольку из самого определения языка L' ясно, что его цепочки подцепочек вида aa не содержат. Следовательно, | имеет вид Ptjy, где р, у е Z. Поскольку ненадчеркнутый символ р стоит непосредственно справа от надчеркнутого символа а, должно быть а = [В, /, k], р = [С, /, /], причем в Г найдется правило
216 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О Б-ГРАММАТИКАХ [ГЛ. 6
вида А—>ВС (действительно, по определению языка L' всякая подцепочка всякой его цепочки, имеющая вид i ctP, именно такова), так что С — правый символ, а В— . левый. Однако совершенно аналогичным образом из того, что а стоит непосредственно справа от у, получается, что символ В правый. Имеем противоречие. Таким образом, L'[)[D(Z)—D'(Z)] = 0, т. e.L'f\D(Z) = = L'f]D'(Z). Следовательно, нам достаточно теперь доказать, что L = U Л D' (Z). Однако из способа построения цепочек х непосредственно ясно, что каждая такая цепочка принадлежит как V, так и D (Z). Остается показать, что любая цепочка фе^Пй'(2) принадлежит L. Для этого мы воспользуемся индукцией по длине ф, причем для удобства проведения индукции будем доказывать несколько более общий факт. Сопоставим каждому символу A стандартный А-язык
La, отличающийся от L' только тем, что V& и Vдг будут состоять теперь из всевозможных скобок вида [A,i,j] и [A,i,j] соответственно. Обозначим через LA(T) множество всех цепочек в V, выводимых в Г из А; для каждой цепочки хе?А(Г) построим х так же, как это делалось для цепочек из L(T), и множество всех таких х обозначим Еа. Покажем теперь, что для любого всякая цепочка y<=LA(}D (Z) принадлежит LA. Тем самым доказательство будет завершено.
Заметим прежде всего, что если г|э — произвольная
“Тц f f
подцепочка какой-либо цепочки из La Л D (Z), сокращающаяся до пустой цепочки, то либо = agci, либо гр = PtjPySy. гДе выделенные вхождения символов а и a, р и р, у и Y соответствуют друг другу (иначе говоря, сокращаются друг с другом). Действительно, в противном случае мы имели бы = a^aPtiPYSY^ но по определению языка L'a в его цепочке лишь тогда может содержаться подцепочка вида бе, когда b = [B,j,k], е = = [С, /, /], где символ В левый, а С правый. Поэтому получаем р = [D, т, п] и символ D оказывается одновременно левым и правым, что невозможно.
Пусть теперь у^Ь'А(] D' (Z). Если I Ф I = 4 (наименьшая возможная длина цепочки из La), то ознд-
КАНОНИЧЕСКОЁ ПРЕДСТАВЛЕНИЕ Б-ЯЗЫКА
217
чает ф = [Л, г, /]аа[А, г, /], причем в Г должно быть правило А->а с номером /; но тогда ф = а, так что Ф е La. Пусть утверждение доказано для всех цепочек
длины, меньшей п (п > 4), и ф е L'a Л D' (Z), причем |ф| = п. Тогда ф = а1ра', где а = [Л, г, /], а' — [А, г', /']. Нетрудно заметить прежде всего, что выделенные вхождения скобок а и а' соответствуют друг другу, так что а = а'. Действительно, в противном случае, по сделанному выше замечанию, скобка, соответствующая а, стояла бы непосредственно слева от скобки, соответствующей а', т. е. ф содержала бы подцепочку И, i, j][A, i', j']; но тогда А должен был бы быть одновременно левым и правым символом. Далее можно усмотреть, что правило с номером j должно иметь вид А-*-ВС, а цепочка ip должна начинаться символом вида [В, /, к] и кончаться символом вида [С, j, /]. В самом деле, в силу определения La в противном случае могло бы быть только гр = а\|/й, причем гр Ф Л, поскольку | ф | > 4. Однако тогда выделенные вхождения а и а должны бы были соответствовать друг другу, иначе в гр нашлась бы подцепочка аа, чего в цепочке из La быть не может, а значит, i|/ сокращалась бы до Л. Однако из определения L' ясно, что г|/ начинается вхождением а, а значит, при сокращении гр это вхождение сократилось бы с каким-то вхождением а, стоящим правее, что невозможно. Итак, гр = [В, /, k] % [С, /, /]. При этом В — левый символ, а С — правый, так что во всяком случае В фС, и, значит, скобки [В, }, k] и [С, j, /] не могут быть соответствующими. Следовательно, % = %1 [В, /, k] [С, /, 1]%2, где и %2 сокращаются до пустой цепочки. Но это означает, что цепочки IB, U k] х, [В, j, к] и [С, /, /] %2 [С, }, I] принадлежат
соответственно Lb[\D'(W) и Lc(]D' {W); следовательно, по индуктивному предположению они принадлежат LB и Lc соответственно. А отсюда — и из наличия в Г правила А -» ВС — следует, что цепочка ф =
= 14 г, j][B, j, ft]xi [В, j, к] [С, j, 1}%2[С, U l][A, i, j] принадлежит LA•
