Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
б) Указать примеры, из которых следует, что при нарушении ; одного из условий пункта а) утверждение этого пункта теряет силу.
6.20. В пространстве формальных рядов в данном-алфавите определить расстояние таким образом, чтобы это пространство стало метрическим.
6.21. Показать, что пространство формальных рядов в данном
алфавите является полным (т. е. в нем имеет место критерий Коши).
6.22. Определим сложение, умножение и адамарово умножение формальных рядов (обозначения: +, X и ® соответ-
ОО оо
ственно) следующим образом: если г = ^ f (п) хп, s= ^ 8 («) хп,
/1=0 /1=0
оо оо
то г + s = 2 (/(«) + ? («)) хп> гХ$ = 2 * (п) хп, где h (п) — сумма п=О /t=0
всевозможных произведений f (/) g (/') таких, что х{х^ = хп, r(g)s =
ОО
= 2 f (п) 8 (и) хп- Показать, что опорные множества рядов г + s,
я=0
rXs и равны соответственно объединению, произведению и
пересечению опорных множеств л и s.
6.23. Показать, что дополнение к языку Дика D (V) можно представить в виде S (L'\ ах, ..ап, ах, ап\ axD (V), ..., anD (V),
axD (V).....anD (V)}, где {ai.....an) — V и L' — стандартный Л-язык
в словаре {а1......ап, ах, ..., ап}. Аналогично для скобочного языка.
6.24. Построить детерминированные МП-машины, допускающие языки D(V), CD(V), D (V) и CD'(V) соответственно.
6.25. а) Показать, что теорема 6.7 останется справедливой, если взять в качестве Г линейною Б-грамматику и заменить D (Z) и D' (Z) языками D, (Z) и Dx (Z) соответственно, где Dx (Z) и d'x (Z) определяются следующим образом: (i) Aeflj (Z), AsDx(Z); (ii) если xeDx(Z), x s d'x (Z) и asV, to axa, Hxa^Dx(Z), ах'й<= D'X(Z); (iii) никакая цепочка не может принадлежать Dx (Z) или D'x (Z) иначе, как в силу (i) или (ii).
б) Сформулировать и доказать аналогичные утверждения для металинейиых Б-грамматик, итерационно-линейных Б-грамматик и .Б-ОАЕВ-грамматик.
6.26. Показать, что если в теореме 6.7 вместо стандартности •языка L' потребовать выполнения более слабого условия — А-опреде^ ленности для некоторого k, зависящего от Т. (см. упражнение 5.7), то словарь Z и язык D (Z) можно выбрать одни и те же для всех Б-грамматик с данным основным словарем.
ГЛАВА 7
СЛОЖНОСТЬ ВЫВОДА В БЕСКОНТЕКСТНЫХ ГРАММАТИКАХ
Для классификации Б-грамматик по сложности вывода «разрешающая способность» «главных» сигнализирующих операторов — временной сложности и емкости — оказывается недостаточной. Действительно, для всякой Б-грамматики Г функция Тг(п) мажорируется линейной функцией (упражнение 4.1,6)) и сверх того для любой Б-грамматики Г можно построить эквивалентную Б-грамматику Г' такую, что Tv(n)<.cn, где с — произвольное наперед заданное положительное число (это тривиальным образом вытекает из теоремы 6.3); но временная сложность грамматики, порождающей бесконечный язык, не может быть по порядку меньше линейной функции (неравенства (1) и (2) на стр. 59). Что же,касается емкости, то она, как мы знаем, не позволяет классифицировать даже неукорачивающие грамматики. Зато квазисигнализирующие операторы «низших» типов — левая и правая глубина, разброс, активная емкость, для которых соответствующие относительные операторы в классе Б-грамматик являются сигнализирующими, — дают в рассматриваемом случае весьма интересную картину. К ее описанию мы и перейдем.
§ 7.1. Глубина и разброс
Левая глубина. Следующая теорема устанавливает связь между левой глубиной Б-грамматики и степенями левого ветвления отвечающих ей систем составляющих.
222 СЛОЖНОСТЬ ВЫВОДА В Б-ГРАММАТИКАХ [ГЛ. 7
Теорема 7.1 (ср. упражнение 3.5). Для всякой Б-грамматики Г = (V,W,I,R)
где d — максимум длин цепочек леР, для которых существуют правила вида Л-*л;0е/?, причем 0 Ф Л. В частности, для стандартной бинарной Б-грамматики
Имеет место даже более сильное утверждение: (Г, х)<Ул(Г, х)+ 1 ^ (Г, х) + d (смысл символов ;
и Ул ясен из систем обозначений, использовавшихся ;. на стр. 55 и 83).
Назовем левой глубиной цепочки хм, где хеУ* и со е W{V\j 1У)*и{Л}, число |ю|. Левой глубиной вывода будем называть наибольшую из левых глубин входящих в него цепочек. Легко видеть, что среди всех выводов в Б-грамматике, отвечающих одному и тому же дереву вывода, наименьшую левую глубину имеет упорядочиваемый вывод (всегда существующий и единственный— см. стр. 119). Поэтому ? нужное утверждение непосредственно получается из следующей леммы.
Лемма 7.1. Пусть (в обозначениях теоремы 7.1)
А е W, х е У+ и Т есть (А, х) -дерево. Тогда
УЛ<УЛ(Т) + 1 <г/л + где ул (Т) — степень левого ветвления индуцируемой де- , ревом Т системы составляющих для х и ул —левая глубина соответствующего Т упорядочиваемого вывода.
Доказательство. Если высота Т равна единице, -неравенства очевидны. Пусть они доказаны для всех (В, г)-деревьев высоты, меньшей п (B^W, zeV+), ? высота Т равна п и а0)> ... )>аА_, — все узлы Т, подчиненные корню. Для- каждого узла аг, помеченного вспомогательным символом, обозначим через у^1 степень левого ветвления системы составляющих, индуцируемой на соответствующей подцепочке х полным (^-поддеревом Т (само это поддерево обозначим Гг), и через yf — левую глубину отвечающего этому поддереву упорядочиваемого вывода. По индуктивному предположению yf < yf + 1 < yf + d. Положим, кроме того, ул = О,
