Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
L2 = CiLlCi U bLxb U с = {аса, beb, с}.
Однако всякое решение нашего уравнения, поскольку оно содержит L2, будет содержать также
L3 = aL2a U bL2b Uc =
= а{аса, beb, c}a\}b {аса, beb, c}b\]c =
= {aacaa, abeba, bacab, bbebb, аса, beb, c}.
Вообще, решение L обязательно должно содержать множества
L1 = W, L2 = f (L1), ..., Ln = f(Ln-J, ...,
которые получаются посредством рекуррентного процесса, причем каждое из них содержит в себе предыдущее. Следовательно, L содержит объединение всех этих множеств — мы обозначим его Iim /(L„). Но это объединение есть не что иное, как «зеркальный
П-> оо
язык» Lm. Итак, всякое решение нашего уравнения содержит Lm, т. е. Lm оказывается наименьшим решением нашего уравнения. Мы будем называть наименьшее решение просто решением1).
Вариант записи. При решении уравнения ?=f(?) мы использовали язык Li = {с}, однако константу мы могли бы получить и иным путем, а именно введя в рассмотрение «идеальный элемент» со2), являющийся нулем относительно конкатенации (т. е. такой, что асо = соа = е, где е — пустая цепочка). Положив
L0 = со,
получим
/(L0) = {acoa U bab U с} = C = Lu что унифицирует запись рекуррентного процесса.
11.1.5. Индуцированная структура
В начале этой главы мы напоминали, что умножение языков и конкатенация цепочек — ассоциативные операции. Если даны три языка L1, L2, L3, то мы имеем
(LiL2) L3 = L1 (L2L3),
') Легко видеть, что это решение — единственное. В самом деле, если L' — какое-либо решение данного уравнения и JteL', то либо х есть с, либо х имеет вид ауа или byb, где у є L'; однако то же верно и относительно у и т. д., так что X должна иметь вид Ztz (гє {а, &}*). Таким образом, L' с L тп, а поскольку Lm — наименьшее решение, то L' = Lm. — Прим. ред.
2) «Идеальный элемент» ш не следует смешивать с пустой цепочкой, которая является единицей относительно конкатенации. Гл. XI. Задание языков с помощью систем уравнений
179
что позволяет не писать скобок. Однако сохранение скобок (или заменяющих их символов) обеспечивает представление в явном виде «истории» получаемых цепочек.
Пусть имеются языки L1, L2, L3, заданные перечислением их цепочек:
= iX 1, Х2г • • • , xU • • •},
1-2 = \Уъ Уь У1, ¦ ¦ ¦},
Lz = {21> 22> • • •, Zk> ¦ • •}•
Образуем произведение L1L2, а затем (L1L2)L3; тогда результирующий язык будет состоять из цепочек XiyjZk, имеющих структуру ((Xiyj)Zh). Если же образовать сначала произведение L2L3, а затем Li(L2L3), то полученный язык будет содержать те же самые цепочки, но с другой структурой: (Хі(у,гк)). Точно так же язык CiLl состоит из цепочек ахі со структурой (а(Хі)) и т. п.
Потребуем, чтобы при решении уравнений типа 2 =/(2) сохранялась структура цепочек, индуцированная самим ходом решения.
Пример решения с сохранением структуры. Решим указанным образом то же уравнение 8 = f( 8):
50 =U>,
51 = {ааа U bab U с) = {(с)},
52 = {а (с) a U b(c) Ь U с} = {(а (с) а), (Ь(с)Ь), (с)},
53 = {а{(а (с)a), (b(c)b), (с)}а, Ь{(а(с)а), (Ь(с)Ь), с}Ь, (с)} =
= {(а (а (с) а) а), (а(Ь(с)Ь)а), (Ь(а(с)а)Ь), (b(b(c)b)b), (а (с) а),
(Ь(с)Ь), (с)} и т. д.
Тем самым мы снабдим структурами все цепочки языка Lm. Эти структуры идентичны тем структурам, которые сопоставляет цепочкам языка Lm порождающая его КС-грамматика с правилами
S—>aSa, S —уbSb, S-+c. Так, для L3 получаются следующие структуры:
S S 180
Часть II. Некоторые замечательные классы языков
Отсутствие пометок при скобках в нашем примере связано с тем фактом, что соответствующая грамматика имеет лишь один вспомогательный символ.
Ясно, однако, что приписывание цепочкам структур наиболее интересно в случае неоднозначных грамматик. Предыдущая грамматика была однозначной, поэтому теперь мы рассмотрим другую грамматику, порождающую «бинарные формулы», т. е. цепочки, получаемые с помощью некоторого бинарного оператора.
11.1.6. Пример для случая неоднозначной грамматики
Рассмотрим следующую КС-грамматику:
^ = VT = {a,b), I 5 -> SaS, S-+b \.
Любой вывод, за исключением вывода 5—*Ь, начинается так:
S
и каждое из полученных 5 может быть началом вывода цепочки, принадлежащей порождаемому данной грамматикой языку. Этому языку отвечает уравнение
2 = 2a8(J&,
которое мы сейчас решим, сохраняя в цепочках структуру, индуцируемую ходом решения. Итак,
S0 = и,
2, = {(oato U b) = {(ft)}, 22={{W}fl{W}U6}=«(6)fl(6)), m,
Z3 = {{((b)a (b)), (Ъ)}а{((Ь)а(Ь)), (&)}U&} = = {(((b) a (b)) a ((b) a (b))), (((b)a(b))a(b)), ((b) а((Ь)а(Ь))\
((b)a (b)), (Ь)} и т. д.
Сняв все скобки, мы получим
83 = {bababab, babab, babab, bab, b}.
Мы видим, что цепочка babab была получена дважды. С теоретико-множественной точки зрения достаточно иметь один ее экзем- Гл. XI. Задание языков с помощью систем уравнений
181
пляр; однако разные экземпляры имеют разную структуру. Первый отвечает выводу
S
b a b а ь
и имеет структуру (((b)a(b))a(b)), а второй получается в результате другого вывода, «симметричного» первому:
