Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
*) Впрочем, аналогичный факт верен и для произвольных НС-грамматик— см. упражнение 3.5, а).
244
СЛОЖНОСТЬ ВЫВОДА В Б-ГРАММАТИКАХ
(ГЛ. 7
что при любом п для всякого дерева вывода цепочки апЬп соответствующая система составляющих будет содержать последовательность составляющих zu ..., zh такую, что: a) h ^ с-2п, где с— константа, зависящая только от грамматики; б) Zi =akibl{, причем ki — ki+i = = ti — U+1 > 0 для всех t — 1, ..., h — 1. Однако из условия б) вытекает, что данная последовательность является гнездом.
. Теперь нам остается исследовать строение множеств lX (Г) и Lk (Г) (смысл этих обозначений ясен по аналогии с введенными на стр. 61). Картина здесь сходна с той, которая была получена для глубины: имеет место
Теорема 7.6. Для любой Ъ-грамматики Г и любого натурального числа k множества Lf (Г) и L.J (Г) являются A-языками. Более того, для всякой Ъ-грамматики Г и всякого натурального k можно построить А-
Ф X
грамматики, порождающие Lk (Г) и Lk (Г) соответственно.
Доказательству предпошлем лемму. Будем называть вспомогательный символ А Б-грамматики Г само-вставляющимся, если имеются такие непустые цепочки ? и т|, что А Ь-?Лт]. Б-грамматику, у которой нет г
самовставляющихся символов, назовем Б-грамматикой/ б е з самовставления.
Лемма 7.3. Для всякой Ъ-грамматики без самовставления можно построить эквивалентную ей А-грамматику.
Доказательство. Пусть Г = ( V, W, I, R)— Б-грамматика без самовставления и р = \x(W). Каков бы ни был символ А е W, из А не могут быть одновременно выводимы цепочки вида %А и Ац, где g ф А, г| ф
Ф Л; и если, например, А 1— ?Л, \Ф А, то g не содер-
г
жит вхождений Л. Поэтому, в частности, если р = 1, т. е. W = {/}, то Г является либо правосторонней, либо левосторонней линейной грамматикой, и можно построить эквивалентную ей автоматную грамматику (стр. 169). ПустЪ утверждение доказано для грамматик с менее чем р вспомогательными символами. Пусть для определенности R не содержит правил вида I —*? /g, \ф А. Сопоставим каждому символу Ле W новый символ А и положим W = {А [Л е W). Положим далее
§ 7.3]
СТЕПЕНЬ ГНЕЗДОВАНИЯ И САМОВСТАВЛЕНИЯ
245
r = (V'U(U7—{/}), W,J,R),_rm R состоит из всевозможных правил вида А —*? фВ таких, что А —? фВ е R, и правил вида 7 —? гр таких, что /-+фе/? и ф не содержит вхождений /.. Кроме того, для каждого Дей7 — {/} будем полагать ГА = (V, W — {/}, A, R'}, где R' получается из R изъятием правил, содержащих в левой или правой части вхождения 1. Для каждой грамматики Гд можно по индуктивному предположению построить эквивалентную ей А-грамматику, и то же верно для правосторонней линейной грамматики Г, однако поскольку в цепочках вывода в Г, начинающегося символом /, этот символ может стоять только на последнем месте, язык L(T) получается из L(T) подстановкой вместо каждого Л е W7—{/} языка /.(Га), и мы можем воспользоваться теоремой 5.4.
Доказательство теоремы 7.6. Пусть Г = = (V, W,I,R) — Б-грамматика. Мы можем считать, что она не имеет правил вида Л->В, B^W. Кроме того, нам удобно будет полагать, что основные символы могут содержаться лишь в правых частях правил вида А —>? а, аеУ; действительно, если ввести для каждого а е V «двойника» — новый символ а, заменить в правых частях всех правил из R не вида А ->а, йб1/, все вхождения основных символов вхождениями их «двойников» и добавить к R всевозможные правила вида а->а, то это не изменит ни порождаемого грамматикой языка, ни ее степени гнездования, ни степени самовставления.
Введем теперь для каждого символа А е W 5(ft + 1) новых символов: Ллн'г («левые неуглубляющие» символы), Ллу'1 («левые углубляющие»), Лпн> 1 («правые неуглубляющие»), ЛПУ' ‘ («правые углубляющие»), Лс'1 («средние»); здесь Каждому правилу Л->
—>ВЕ{ ... ESD, где В, Еи Es, D^W, s^O, сопоставим 5ft новых правил:
i = 0 ft — 1
246
СЛОЖНОСТЬ ВЫВОДА В Б-ГРАММАТИКАХ
[ГЛ. ?
Кроме того, каждому правилу Л—>а, где ае7, сопоставим всевозможные правила вида Лъ-‘—>а, где
Ъ = ЛН, ЛУ, ПН, ПУ, С и i — 0, k.
Положим теперь Г' = (У, W, /с- °, R'), где W' состоит из всех новых символов и R' — из всех новых правил.
Из самого вида новых правил непосредственно усматривается, что при любом / = 0, ..., k — 1 цепочка, выводимая в Г' из символа Ллн’ соответственно Лпн> {, может содержать вхождение того же символа только на первом, соответственно последнем, месте; символы же Ллу, ^ лпу, ^ Ас. i (г = 0, ..., k), а также Ллн•k и Лпн'k не являются даже циклическими. Поэтому Г' —грамматика без самовставления, и по лемме 7.3 можно построить эквивалентную ей А-грамматику.
Вспомнив индуктивное определение степени гнездования составляющей (стр. 289), можно без всякого труда показать индукцией по i, что в любом дереве полного вывода в Г7 степень гнездования каждой состав- ? ляющей, «происходящей» от узла, помеченного символом с индексом i, равна t; поэтому степени гнездования деревьев полных выводов в Г' (точнее, отвечающих им систем составляющих) не превосходят k. В то же время, если в дереве вывода в Г' лишить все символы-метки индексов, получится дерево вывода в Г, имеющее, очевидно, ту же степень гнездования; следовательно, L(P)sL?(r). С другой стороны, легко показать, что во . всяком дереве полного вывода в Г, степень гнездования которого не превосходит k, можно так снабдить символы-метки индексами, чтобы получилось дерево полного вывода в Г' (следует приписывать индексы «сверху вниз», переходя от каждого узла к подчиненным ему). Отсюда bf (Г') s L (Г').
