Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Замечания. 1. Сопоставляя конец доказательства леммы 6.5 с леммой 6.2 (пункты б) ив)), видим, что если G = (Г, /) — Д-грамматика ограниченной ширины, то степень Г не превосходит ширины G. Отсюда по лемме 6.3 вытекает, что если Г — приведенная удлиняющая Б-грамматика, то ширина Д-грамматики, сильно эквивалентной Г, не может быть меньше степени Г.
2. Характеристикой Д-грамматики, в известном смысле двойственной ширине, является ее высота — максимум высот соответствующих деревьев подчинения. Если такой максимум существует, естественно сказать, что Д-грамматика имеет ограниченную высоту.
О возможности построения сильно или слабо эквивалентной Д-грамматики ограниченной высоты для данной Б-грамматики см. упражнение 7.7.
§ 6.4. Системы уравнений в языках.
Формальные степенные ряды
Сейчас мы покажем, что ОБ-грамматики можно интерпретировать как своеобразные системы уравнений, в которых коэффициентами и неизвестными являются языки. Такой интерпретацией, вернее, подсказываемым ею способом записи, особенно охотно пользуются специалисты по языкам программирования.
Фиксируем словарь V = {а\,..., as} и конечный набор переменных 8 = {Si, ..., in}- Рассмотрим п многочленов от этих1 переменных, или, как мы будем здесь говорить, неизвестных, с коэффициентами, представляющими собой непустые конечные языки в словаре V: f 1 (Ei, .... gn).Mil.......|n). (He требуется,
208 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О Б-ГРАММАТИКАХ [ГЛ. 6
чтобы каждый многочлен действительно содержал все неизвестные или даже чтобы каждая из них присутствовала хотя бы в одном многочлене.) Для каждого из многочленов fi, fn существует тождественно равный ему многочлен, коэффициенты которого являются цепочками (точнее, одноэлементными языками) в У; мы будем считать, что коэффициенты всех ft с самого начала таковы.
Рассмотрим теперь систему уравнений
Mi .......In) — li>
(*)
fnibii •••» in) !»•
Такую систему мы будем называть нормальной. Ее решением естественно назвать всякую упорядоченную п-ку (Li, ..., L„) языков в словаре V, подстановка которой вместо (gi, • • •, in) обращает каждое уравнение системы в тождество, т. е. такую, что L„) =
= Lj для каждого / = 1, ..., п.
Покажем прежде всего, что система (*) имеет по меньшей мере одно решение, которое можно найти «методом последовательных приближений». Именно:
определим последовательность п-ок языков 5?(0), i?(1)..
где S’(i) = (L(/), L{n), следующим образом: (I) 3?{0) =
<0......0); (II) г“+" «(№/’, .... ii"), ...JjL1!', ...
.... L«%
Поскольку всякий многочлен является неубывающей функцией*), из очевидных соотношений ...
L^n s iJn вытекает .....и т. д.;
иначе говоря, для каждого/ — 1, ..ппоследовательность Lf\ ..L/’, ... является неубывающей. Положим теперь
==L/0) (JL/1* U • • • (/ = 1, ..п). Тогда, с одной стороны, имеем Ly'sL/ для всех j— 1, ..., п\ i — 0, 1,
Функция g(Xlt Xk), аргументы и значения которой суть множества, называется неубывающей, если из X] s х\,...
xk^x'k следует ..., X?). Это свойство
очевидным образом имеет место для объединения и произведения 9 значит, и для любого многочлена-
СИСТЕМЫ УРАВНЕНИИ В ЯЗЫКАХ
209
откуда Lj = (Jf/W0, Ln); с дру-
i=°
гой стороны, если z^fj(Lu L„), то найдутся такие цепочки ^eZ,, x„eL„, что г е=//(*,, ...,*„); но отсюда, обозначая через t0 наименьшее ?, для которого- е Li‘), ..., xn<=Ln\ получаем г <= ...
•••> 4'0))e4<0+1)si/- Итак> li = fiCLu I*).
Нетрудно видеть, далее, что если (Lj, ..Ln) — произвольное решение системы (*), то Z,! ? Lj, ..L„ ? L„; действительно, тривиальным образом L^sLj, ...
..., Lj? ?= Lf, отсюда L(,u = f, (L?“, ..., Lj,0)) s f,(L„ ...
..., Ln) = L\, ..., ..... Lf)<=fn(Lu •••
..., L„) = 1, ит. д., откуда и получаются нужные соотношения. Это дает основание назвать решение (Lb ...
... Хп) системы (*) наименьшим.
О существовании других решений см. упражнение 6.19.
В дальнейшем нам удобно будет считать, что в многочленах «раскрыты все скобки», т. е. что каждый из них представлен в виде объединения выражений вида где 5 0, 1, . • •, Xq, ..., xr s V
(см. стр. 25), которые мы будем называть членами Члены, не содержащие неизвестных, называются свободными.
Требуемое представление многочлена, очевидно, единственно с точностью до перестановки членов.
Сопоставим теперь системе (*) ОБ-грамматику Г =(V, Е, \\,К), где R состоит из всевозможных правил вида ij—*?«» таких, что /= 1, ..., п и га — член многочлена fj. Обозначим через Lj(Y) множество всевозможных цепочек в словаре V, выводимых в Г из
Ясно, что для каждого / — 1, ..., п язык Lf] есть не что иное, как множество свободных членов f}, а последнее совпадает с множеством правых частей заключительных правил Г, имеющих левой частью т. е. цепочек в V, выводимых в Г из ^ за один шаг,—иначе говоря, с помощью деревьев вывода высоты 1.
210 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О Б-ГРАММАТИКАХ [ГЛ. 6
Покажем, что для любого i = 0, 1, ... язык L\l) есть множество цепочек в V, выводимых в Г из gj с помощью деревьев вывода высоты, не превосходящей г-f 1. Действительно, пусть утверждение доказано для всех
