Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Займемся теперь степенью самовставления. Пусть W — {#i, .. ., Яр}. Каждому А — Hi ^ W мы сопоставим систему новых символов, которые будут запи-(s1 ... sp\
сываться в виде Лъ . . I. где Ъ = ЛН, ЛУ, ПН,
Vi • • • ^pl
ПУ, С; Sj = 0, 1; ij = 0, ..., k. (Содержательный
§ 7.3] СТЕПЕНЬ ГНЕЗДОВАНИЯ И САМОВСТАВЛЕНИЯ 247
смысл Ъ — тот же, что и в первой части доказательства; ij означает «степень Я^-самовставления» составляющей, происходящей от узла с меткой А, т. е. наибольшую глубину гнезда, все члены которого «происходят» от узлов с меткой Hj и содержат данную составляющую; Sj — вспомогательный «индекс готовности», смысл которого будет ясен из дальнейшего.) Далее, каждому правилу г = Л->ше^, где a — BEi... ... ESD, В, Ei, ..., Es, D e W, s ^ 0, будет сопоставляться система новых правил, каждое из которых отличается от г только наличием индекса Ъ и матрицы
правую часть; при этом в левой части возможны любые комбинации индексов и матриц, а в правой индексы и матрицы выбираются следующим образом.
I. Значение Ъ для каждого вхождения символа в со выбирается в зависимости от расположения этого вхождения и от значения того же индекса при А точно так же, как в первой части доказательства.
II. Правила выбора значений Sf
1) Для всех средних вхождений Sj = 1 (/=!,...
2) Если А = Hj или значение Sj при А равно 0, то неуглубляющие левые и правые вхождения символов в со получают значения Sj, равные 0, а углубляющие — равные 1.
3) Если А Ф Hj и значение Sj при А равно 1, то все вхождения символов в со получают значения Sj, равные 1.
III. Правила выбора значений iy.
1) Если А = Hj, то значения ij для тех вхождений символов в со, для которых Sj = 0, такие же, как для А, а для тех, для которых Sj = 1, — на единицу больше.
2) Если А ф Hj, то для всех вхождений символов в со значения ij такие же, как для А.
При этом, если А = Hj и значение ij для А равно k, то те из описанных выше правил с соответствующей ле« вой частью, у которых в правой части имеются вхождения Hj со значениями Sj, равными 1, изымаются из числа сопоставляемых правил.
при каждом вхождении символа в левую и
..., р).
248
сложность ВЫВОДА в б-грамматиках
[ГЛ. 7
Кроме того, каждому правилу вида А->а, где ае1/, сопоставляем всевозможные правила вида
Лъ(5‘ Sp)->a.
Vi ••• V
Положим Г' = [V, W', Iе I 0 о I# /’ где W' со
стоит из всех новых символов и R' — из всех новых правил.
Из приведенного только что описания новых правил легко усматривается, что:
а) если левая часть правила имеет вид „ли I si • • • sp \
Я/ . . I. то у всех вхождении символов в пра-
V h • •• lp 1
вую часть, кроме первого (также имеющего JIH в качестве значения Ъ) значения ij больше, чем в-левой части, а значения ii, ..., ij+i........ip такие же; б) для
гг ПН ( S1 • • • Sp\
правил с левой частью Я/ . . рассмотрение
... ipj
симметрично; в) если левая часть имеет вид
7ъ I si • • • sp
Я/ . .1, где Ъ равно ЛУ, ПУ или С, то в правой
\г1 • • • 1р/
части первое и последнее вхождения символов имеют в качестве значений Ъ ЛН и ПН соответственно, и значения t'i, ..., ip у этих вхождений такие же, как в левой части, а у средних вхождений значения ij больше, чем в левой части, и значения остальных i такие же. Отсюда, в свою очередь, ясно, что символы, для которых Ъ равно ЛУ, ПУ или С, не циклические и что в цепочке, выводимой из символа, для которого Ъ = ЛН (соответственно Ъ = ПН), вхождение того же символа может стоять только на первом (соответственно последнем) месте. Таким образом, Г' есть грамматика без самовставления.
Нетрудно, далее, показать, исходя опять-таки из самого определения новых правил, что если a — произвольный узел дерева полного вывода в Г', |3 — узел, подчиненный a, taj— «степень Я^-самовставления» узла а (т. е. наибольшая глубина гнезда, все члены которого «происходят» от узлов, несущих п(?метку Hj — с разнь!-,
УПРАЖНЕНИЯ
249
ми, вообще говоря, индексами и матрицами, — и содержат составляющую, «происходящую» от а) и t$j — «степень Я^-самовставления» узла р, то t$j = tai, когда значения ij для меток при аир равны, и t$j = taj -f 1 в противном случае (т. е. когда значение ij для метки при р на единицу больше, чем для метки при а). Отсюда очевидной индукцией получается, что максимум «степеней Я^-самовставления» узлов дерева полного вывода в Г', взятый по всем узлам и по всем / = 1, ..., р, равен наибольшему из значений г'ь ..., ip для меток в узлах данного дерева, так что ни для какого дерева полного вывода в Г7 этот максимум — обозначим его М — не может превосходить k. В то же время, лишив в таком дереве все символы-метки индексов и матриц, получим дерево полного вывода в Г, степень самовставления которого равна М. Поэтому L (гО s bf (Г). С другой стороны, нетрудно показать, что в дереве полного вывода в Г, степень самовставления которого не превосходит k, можно так снабдить символы-метки индексами и матрицами, чтобы получилось дерево полного вывода в Г'; отсюда L* (Г) Е Z. (г ). Доказательство закончено.
Следствие, а) Для любой Ъ-грамматики Г, для которой Фг (п) ограничена числом k, можно, если известно k, построить эквивалентную ей А-грамматику.
