Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
ГЛУБИНА Й PA3SPOC
223
если ai помечен основным символом. Имеем, очевидно, ул = max (г -f ул), ул(Г) = max (г -f ул), причем в первом случае максимум берется по тем г, для которых а* помечены вспомогательными символами, а во втором — по всем / = 0, k — 1. Обозначим через ул' максимум чисел I + ул по тем г, для которых аг помечены вспомогательными символами, и через ул"—максимум тех же чисел по остальным i (если они есть). Тогда ул^ул' + + 1^Ул + 1- С другой стороны, ул'<г/л(Г)-М-1; что же касается числа ул", то оно, очевидно, меньше ул', если узел ak-x помечен вспомогательным символом, и равно k — 1 в противном случае. Но если г0 — наибольшее г, для которого щ помечен вспомогательным символом, то k — 1 — i0^d и /0^#л—1, так что (k — 1) -f 1 = k < ул -f d. Этим доказательство заканчивается.
Связь между левой глубиной и степенью левого ветвления была впервые замечена В. Ингве [Yngve I960]; именно эта связь была выдвинута им в качестве основного аргумента для обоснования гипотезы об ограниченности степеней левого ветвления в естественных языках (стр. 290). Дело в том, что если моделировать процесс произнесения («порождения») предложения человеком с помощью вывода в Б-грамматике, то для каждой промежуточной цепочки вывода ее отрезок вправо от самого левого вхождения вспомогательного символа (включая это вхождение) естественно интерпретировать как ту информацию, которую говорящий должен на соответствующем шаге процесса держать в памяти. [Такая интерпретация будет особенно наглядной, если взять грамматику с правилами вида Л —>хХ, где JteV* и X <= W* (например, стандартную бинарную ' или в нормальной форме), и построить для нее эквивалентную МП-машину способом, использованным в доказательстве теоремы 6.4. Тогда каждая промежуточная цепочка упорядочиваемого вывода будет иметь вид zZ, где г е е У* и Z е W*, а при переходе к МП-машине цепочка Z (точнее, Z) станет содержимым рабочей ленты, т. е. «ленты памяти», на соответствующем шаге вычисления.] Но объем «оперативной памяти» человека ограничен сверху, причем граница, по данным экспериментальной психологии, сравнительно невысока. То
224
СЛОЖНОСТЬ ВЫ66ДА в б грамматиках
[ГЛ. 1
обстоятельство, что гипотеза в целом не подтверждается (стр. 290), заставляет сделать вывод, что с помощью Б-грамматик — во всяком случае, без дополнительных механизмов — нельзя достаточно удовлетворительно моделировать процесс порождения предложения носителем языка *).
Тем не менее Б-грамматики, левые глубины которых ограничены константами, представляют значительный лингвистический интерес, хотя бы потому, что ограниченность степеней левого ветвления является существенной типологической характеристикой языка. Возникает вопрос о природе языков, порождаемых такими грамматиками, а также множеств цепочек, выводимых в произвольных Б-грамматиках с помощью выводов ограниченной левой глубины. Ответ на эти вопросы дает следующая
Теорема 7.2. Для любой Ъ-грамматики Г и любого натурального числа k множество L%R является A-языком. Более того, для всякой Ъ-грамматики Г и всякого натурального k можно построить А-грамматику,
порождающую (Г).
Доказательство. Пусть Г = (V, W, I, R). Сопоставим каждой цепочке a)e(VUlF)+, новый
символ а(ю) и каждой тройке (cp, ip, х), где cpe(VUW)+, гр&(V\JW)*,x е V*, |ср|, |ip|<;& и cp|=xi|), новое пра-
Г
вило а(ср)-*ха(гр), если гр ф Л, и а(ф) —*х, если \р = Л. Положим Г'= (V,W',a(JJ,R'), где W' состоит из всех новых символов и R' — из всех новых правил. Грамматика Г' правосторонняя линейная, и для нее без труда строится эквивалентная ей автоматная (ср. стр. 169). В то же время легко видеть, что L(T') = L(T).
Следствие. Для любой Ъ-грамматики Г, для которой (п) ограничена числом k, можно, если известно k, построить эквивалентную ей А-грамматику.
*) Это утверждение ни в коей мере не означает отрицания лингвистической значимости Б-грамматик. Грамматики, неадекватные для моделирования процесса порождения предложения человеком, могут быть в то же время пригодны для описания структуры законченного предложения, подобно тому, как с помощью языка математической логики можно представить готовое доказательство теоремы, но не процесс его нахождения математиком.
ГЛУБИНА И РАЗБРОС
225
Заметим, что если Г — приведенная грамматика, то °У^(п)= 1 тогда и только тогда, когда Г — А-грамма-тика. Таким образом, если С — класс всех функций-констант, то 9!усп (Б) = S (А).
В общем случае для Б-грамматики Г имеем, очевидно, (п) ^п, и существуют Б-грамматики, для которых это неравенство переходит в равенство, — примером может служить хотя бы грамматика Г = ({а}, {/}, /, {/ —>/а,/ —?а}); впрочем, язык ?(Г) = а+ может быть порожден и А-грамматикой, т. е. грамматикой левой глубины 1. Естественно спросить, существуют ли Б-язы-ки, не порождаемые никакими Б-грамматиками Левой глубины, меньшей п. Ответ на этот вопрос отрицателен; более того, для любой Б-грамматики Г и любого действительного числа с, 0<с<1, можно построить Б-грамматику Г', эквивалентную Г и такую, что для всех достаточно больших п имеет место неравенство <У^,(п)^сп (так что для любой линейной функции
