Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
f(n) —сп, с > 0, имеем (Б) = & (Б). [A fortiori это утверждение верно также для разброса и активной емкости.] Действительно, нужным свойством будет обладать всякая грамматика, удовлетворяющая требованию теоремы 6.3, если только взять фигурирующее в условии этой теоремы число s достаточно большим (например, положить
В то же время существуют Б-языки (и даже линей ные языки), удовлетворяющие тому условию, что для каждой порождающей такой язык Б-грамматики ее левая глубина мажорирует некоторую линейную функцию. Приведем пример.
Пример 1. Рассмотрим язык L = {апЬп\ п — 1, 2,...} и произвольную порождающую его Б-грамматику Г = ({а, Ь), W, /, R). Мы можем считать, что Г — приведенная грамматика без правил вида А—*В, A, Bef; действительно, при переходе от произвольной Б-грамматики к приведенной (лемма 4.8) множество полных выводов не меняется, а переход к грамматике без правил вида А—*В можно, как показывает очевидный анализ доказательства леммы 4.1, осуществить так, чтобы
8 А. В. Гладкий
226
СЛОЖНОСТЬ ВЫВОДА fi б-грАМмаТйках
[ГЛ. 1
между множествами полных выводов в старой и новой грамматиках существовало взаимно однозначное соответствие со следующим свойством: для каждой цепочки и» из полного вывода в старой грамматике найдется цепочка со' из соответствующего вывода в новой такая, что |о/| = |й>| и на всех местах, на которых в а стоят основные (соответственно вспомогательные) символы, в и>' также стоят основные (вспомогательные) символы, и обратно.
Покажем прежде всего, что ни из какого символа А е W не может быть выводима цепочка вида <рВг|)Сх, где В я С — циклические вспомогательные символы. Действительно, в противном случае мы имели бы А |— xByCz, В К щВи2, С 1— ViCv2, где х, у, z, щ, и2, Vi, v2 е V*, uiu2 ф Л ф vxv2. Кроме того, /|— t\At2, В\—г, С У~ s, где tu t2l г, seV*. Но тогда / Ь- tixUiBu2yuiCu2zt2 и tlxuiru2yvisu2zt2 = anbn для подходящего п. Поэтому ЛИбО 11\Ги2 СОСТОИТ ТОЛЬКО ИЗ а, ЛИбО ViSU2 — только из Ь\ и если, например, справедливо первое, то оказывается невозможным tlxu\ru22yvlsv2zt2^ L, что по предыдущему должно иметь место.
Пусть теперь Т — произвольное дерево вывода цепочки апЬп из / в Г. Из предыдущего следует, что, каковы бы ни были два пути в Т, идущих из корня в узлы, помеченные циклическими символами, один из них является продолжением другого. Наибольший из таких путей назовем главным. Никакое поддерево с корнем в произвольном узле а главного пути, состоящее из всех узлов, зависящий от а и не входящих в главный путь, не содержит узлов, помеченных циклическими символами, так что высота такого поддерева не превосходит числа p = \i(W), и поэтому оно содержит не более q = 1 + g + g2 -f ... -^-gp узлов, где g — максимум длин правых частей правил Г. Следовательно, главный путь содержит ье менее kl(q-\- 1) узлов, где k — общее число узлов дерева Т. Далее для подходящего символа A найдется последовательность aj, ..., а/, узлов, лежащих на главном пути, упорядоченных «сверху вниз» и помеченных этим символом, такая, что для каждого i = О, ..., h — 1 длина пути из а* в а,+1 не
превышает р, откуда h ^ ck, где с = ц > и тем бо-
ГЛУБИНА И РАЗБРОС
227
лее h ^ с-2л; важно заметить, что с — константа, не зависящая от л и от Г.
Обозначим через z{ составляющую цепочки апЬп, «происходящую» от аг. Рассуждениями, аналогичными использованным в начале разбора примера, без всякого труда устанавливается, что для любого г = 1, ..., h будет Zi — ak‘bli, причем — kl+l = /г — /г+1 для всех
i = 1....h — 1. Поэтому, во всяком случае, lt — /г+, > 0.
Пусть теперь (/ = м0, ....... = апЬп) — произвольный
вывод, отвечающий дереву Т, и o)/).......оа/ — те его
цепочки, которые «проходят» через аь ..., ал соответственно. Если в цепочках му. и ®/г+1 выделить те вхождения Л, которые отвечают узлам щ и аг+1 соответственно, то мы получим юу =|Лт1, м/.+[ = l%AQrf, где
g Ь- X', т) I— х\', А 1— ?Л0; при этом 0 Ф Л, поскольку
0 I— bl‘~l‘+1 Ф Л. Следовательно, цепочка мЛ будет содержать подцепочку вида Л0Л_[0Л_2 ... 0j, где все 0{ непусты, так что левая глубина этой цепочки, а значит, и всего вывода не меньше h^c-2n. Таким образом, (п)^сп. [См. также упражнение 7.2.]
Для правой глубины картина такая же, как для левой, с точностью до обращения.
Разброс. Нетрудно видеть, что роль, которую по отношению к глубине играют Л-языки, по отношению к разбросу принадлежит линейным языкам. Именно, справедлива
Теорема 7.3. Для любой Б-грамматики Г и любого натурального числа k множество L* (Г) является линейным языком. Более того, для всякой Б-грамматики Г и всякого натурального k можно построить линейную Б-грамматику, порождающую L* (Г).
Доказательство. Пусть Г = (У, W, /, R). Определим новые символы а(ш), как в доказательстве теоремы 7.2. Каждой четверке (ср, if>, х, у), где фе(Уии?)+, ip<=(VUW)*, х, г/eV*, |ф|, |\|э|</г и ф)= лт-фг/, сопоставим новое правило а(ф)—>xa{ty)y, если г|з ф Л, и а(ф)—*ху, если гр = Л. Положим Г' = (V, W', a(I), R'), где W' состоит из всех новых символов и R' — из всех новых правил. Эквивалентность Г и Г' очевидна.
