Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
есть LP, а предел неубывающей последовательности множеств*) равен объединению всех членов последова-
*) То есть такой, в которой каждый предыдущий член содержится в следующем.
КАНОНИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ Б-ЯЗЫКА
213
тельности. Поэтому опорное множество ряда г/ есть Lt. Что же касается коэффициента при (произвольной) цепочке хп в ряде rt, то он, как легко понять, равен числу (?г, х„)-деревьев в соответствующей ОБ-грамма-тике, т. е. числу существенно различных способов вывода в этой грамматике цепочки хп из символа В част^ ности, для однозначной грамматики коэффициенты ряда Г[ принимают только значения 0 и 1.
§ 6.5. Каноническое представление Б-языка
Цель настоящего параграфа — доказать теорему, которая дает любопытное представление Б-языка, называемое иногда каноническим. Предварительно введем некоторые определения.
Пусть V — произвольный словарь, V& и V&—подмножества V и Р — подмножество V2. Обозначим через L'(V, VVsr, Р) множество тех цепочек в V, которые начинаются символами из V&, кончаются символами из W и содержат только такие подцепочки длины 2, которые принадлежат Р,—иначе говоря, L'{V,V&, V&-, Р)= ^VvV'tWysrttiy'-V'^-PW*). Ввиду теоремы 5.4 L' (V, V&, Vgr, Р) является A-языком; мы будем называть такой A-язык стандартным.
Сопоставим далее каждому символу оеУ «двойника» — новый символ а ф V — и определим два языка D(V) и D'(V), которые будем называть соответственно языком Дика и скобочным языком, следующим образом: (i) пустая цепочка принадлежит обоим языкам; (ii) если цепочки ху и х'у' принадлежат D(V) и D'(V) соответственно, то для произвольного аеУ цепочки хаау и хаау принадлежат D(V), а цепочка х'аау' принадлежит D'(V); (iii) никакая цепочка не может принадлежать ?>(V) или D'(V) иначе, как в силу
(i) или (ii). Очевидно, язык Дика есть не что иное, как множество слов, равных единице в свободной группе с системой образующих V (если считать а и а взаимно обратными); скобочный язык, если интерпретировать а и а соответственно как левую и правую скобки с меткой а, будет представлять собой множество всевозможных «правильных последовательностей» скобок с метками из V.
214 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О Б-ГРАММАТИКАХ [ГЛ. 6
Теперь мы можем сформулировать теорему.
Теорема 6.7. Для всякой Ъ-граиматики Г с основным словарем V можно построить такой словарь ZzoV и такой стандартный A-язык L' в словаре, содержащем Z, что L(T) является проекцией пересечения L' [) D (Z) на V и при этом L' Л D(Z) = L' Л D'(Z).
Доказательство. Для упрощения конструкции будем считать, на что мы имеем право, что Г =
= (V, W,I,R) есть стандартная бинарная Б-грамматика. Сверх того, допустим, что если для какого-либо символа В eW имеется правило вида А —? ВС, то не может существовать правила вида E—*FB\ требуемое для выполнения этого условия преобразование грамматики читатель проведет без труда. Символ Bef будем назы- , вать «левым», соответственно «правым», если имеются ; правила вида А—*ВС, соответственно А—>СВ. Занумеруем как-либо правила Г. Рассмотрим произвольную цепочку хеЦГ) и произвольную систему составляющих этой цепочки, отвечающую некоторому ее дереву вывода. Расставим в х скобки, отвечающие всем состав- . ляющим данной системы (включая тривиальные). Каждую скобку пометим тройкой (A,i,j), где А — метка ° в узле, от которого «происходит» соответствующая составляющая, /— номер правила, применяемого в данном узле, и i — номер правила, применяемого в узле, подчиняющем данный; у сЪэбок, ограничивающих полную составляющую, значение i может быть произвольным, но непременно одинаковым для обеих скобок. Левую и правую скобки с метками A, i, / будем писать в виде [A,i,j] и [Л, I, /] соответственно. Далее вставим непосредственно справа от каждого вхождения сим- • вола а в цепочку х (левее ближайшей скобки) новый ; символ а — «двойника» а. Полученную цепочку сим- • волов и скобок обозначим через х, а множество всех таких цепочек (для всех х е L (Г)) — через %. Имеем, очевидно, х = Tlpvx, так что L(T) = Y\pv L.
Пусть, например, Г содержит правила: (1) I-+AB,
(2) А->а, (3) В->Ь-, тогда одна из возможных Цепочек ab будет иметь вид [/, 3, 1][Л, 1, 2\аа[А, 1, 2][В, 1, 3] ЬЬ[В, 1, 3][/, 3, 1].
КАНОНИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ Б-ЯЗЫКАГ
215
Положим теперь Z = V\JV', V — V \JV \JV'\JV', где V — множество «двойников» основных символов, а V' и V — соответственно множества (типов) левых и правых скобок, помеченных тройками, как описано выше. Определим стандартный A-язык L' = L'(V, V&, V&-, Р) следующим образом: а) Множества V& и V&? будут со-стоять из всевозможных скобок вида [/, i, j] и [/, i, j] (с произвольными i, /) соответственно, б) Множество Р будет состоять из цепочек, сопоставляемых правилам Г следующим образом: 61) каждому правилу с номером /о, имеющему вид Л-*ВС, сопоставляются всевозможные цепочки
[Л, i, /о] [В, /о, k\, [В, /о, k\ [С, /о, /], [С, /о, /] [Л, г, /0],
где i, k, I пробегают соответственно номера всех правил, номера всех правил с левой частью В и номера всех правил с левой частью С; 62) каждому правилу с номером /о, имеющему вид Л—*а, сопоставляется цепоч-ка аа и всевозможные цепочки [Л, г, jo] a, a[A,i,jo], где i пробегает номера всех правил.
