3
Алгебраическая теория
контекстно-свободных языков!)
Н, К оме кий, М. П. Ш ютценберже
1. ЛИНГВИСТИЧЕСКОЕ ОБОСНОВАНИЕ
В предлагаемой работе мы рассмотрим несколько типов
устройств для порождения предложений, тесно связанных с раз-
различными грамматиками естественных и искусственных языков
различных типов. Под язм«о.м_мы__будем понимать просто мно-
множество цепочек, состоящих из символов, принадлежащих неко-
торо~му конечному множеству V, называемому словарем языка;
под гражлштсой^^^множество гцзавил, которые рекурсивно
перечисляют~цепочки, принадлежащее языку. Мы будем гово-
говорить, что~грамматика порождает эти цепочки. (В применении
к естественным языкам порожденные цепочки называются пред-
предложениями; в алгебре их обычно называют словами, а сло-
словарь — алфавитом; когда_?еч^_идет_о_гламматике-лля_яаыка
программирования, цепочки называют программами^, мы же,
кшГпранТГло, будем пользоваться нейтральным термином це-
цепочки))
Если некоторый класс грамматик представляет лингвистиче-
лингвистический интерес, то должна существовать процедура, приписываю-
приписывающая каждой паре (б, G), где б — цепочка, а О — грамматика
этого класса, удовлетворительное структурное описание цепоч-
цепочки б в данной грамматике О. В частности, структурное описа-
описание должно указывать, что цепочка б является правильно по-
построенным предложением языка L(G), порождаемого О. Если
цепочка построена правильно, структурное описание должно
также содержать грамматическую информацию, позволяющую
объяснить, как б понимается носителем языка, пользующимся
грамматикой G; в противном случае структурное описание
>) Chomsky N., Schiitzenberger M. P., The algebraic theory of
context-free languages, Computer programming and formal systems, Amster-
Amsterdam, 1963, p. 118.
Эта работа частично финансировалась управлением войск связи Армии
США, научно-исследовательским управлением Военно-воздушных сил, науч-
научно-исследовательским управлением Военно-морского флота, а также Нацио-
Национальным научным фондом и Государственным фондом.
' 13* Зэк 143

196
Н. Хамский, М. П. Шютценберже
должно показывать, в какой степени б отклоняется от правил
построения предложения.
Мы будем рассматривать только одни аспект структурного
описания предложения, а именно то, как выполняется подраз-
подразделение предложения на словосочетания (фразы), принадле-
принадлежащие к различным категориям. Так, например, структурное
описание английского предложения "those torn books are
completely worthless" должно указывать, что those — это де-
детерминатив, torn и worthless — прилагательные, books — суще-
существительное, completely — наречие, those torn books — группа
существительного, completely worthless — группа прилагатель-
прилагательного, are completely worthless — группа глагола, вся цепочка —
предложение, и т. д. Эта информация может быть представле-
представлена графически:
. Пр .
i—Pp. сущ.
I i
+ + +
Дет. Поил. Сущ,
i i i
+ + +
those torn books
.—/ p. глагола—
I
j—Pp. прил.— A)
Hap. Прил.
i J
completely worthless
или, что то же самое, с помощью скобок:
[Пр.[Гр. сущ. [Дет. those] [Прил. {ат][Сущ. books]][Гр глаг
are [Гр. прил. [Нар. сотрЫе1у][Ярил. worthless]]]]. B)
Основной задачей общей теории естественных языков
является определение: класса возможных цепочек (установле-
(установлением универсального фонетического алфавита); класса возмож-
возможных грамматик; класса возможных структурных описаний; про-
процедуры приписывания предложениям структурных описаний,
если дана грамматика. При этом определение должно быть та-
таким, чтобы структурное описание, приписанное предложению
грамматикой естественного языка, давало возможность объяс-
объяснить, как говорящий на этом языке понимает данное предло-
предложение (без ограничений на память, внимание и т. д.). Тогда
грамматика будет отражать некоторые стороны понимания
языка его носителем.
Здесь нас не интересует эмпирическая проверка адекватно-
адекватности структурных описаний или грамматик, которые мы будем
сследовать. В действительности классы грамматик, которые
ы оудем рассматривать, и типы структурных описаний, кото-
Алгсбраическая теория контекстно-свободных языков
197
рые они порождают, конечно, слишком узки, чтобы судить
о том, как на самом деле люди понимают язык. Тем не менее
рассматриваемые нами системы (формализующие традицион-
традиционные понятия грамматического разбора и анализа по непосред-
непосредственным составляющим) некоторым образом связаны с систе-
системами, которые, по-видимому, адекватны, но в настоящее время
слишком сложны для формального изучения ').
В представлении B) имеются, кроме скобок, две категории
обозначений: 1) символы порождаемых цепочек (т. е. шесть
символов those, torn, books, are, completely, worthless) 2);
2) символы Пр., Гр. сущ., Дет., Прил., Сущ., Гр. глаг., Гр. прил.,
Нар., представляющие категории словосочетаний. Символы
типа A) будем называть терминальными; символы типа B) —
нетерминальными.
Далее, мы будем допускать, что грамматики всех рассмат-
рассматриваемых языков строятся с помощью фиксированного запаса
терминальных и нетерминальных символов. Можно рассматри-
рассматривать множество терминальных символов как потенциальный
общий словарь для всех языков. Для устного языка мы можем
считать, что множество терминальных символов задается с по-
помощью некоторого универсального фонетического алфавита
(предполагая, конечно, что длины морфем ограничены свер-
сверху) 2). В применении к естественным языкам мы можем рас-
рассматривать фиксированное множество нетерминальных симво-
символов как универсальное множество категорий, из которых выво-
выводятся типы словосочетаний (фраз) всех языков.
Важным и традиционным вопросом общей лингвистики
является вопрос о возможности дать конкретную интерпрета-
интерпретацию нетерминальным символам, образующим категории, в тер-
терминах которых строятся грамматики, — другими словами, во-
вопрос о том, можно ли найти общее определение, не зависящее
от конкретного языка, для таких категорий, как Существитель-
Существительное, Глагол и т. д., в терминах их семантического содержания
или формальных свойств грамматик. Проблема конкретной ин-
интерпретации множества терминальных н нетерминальных сим-
') Более подробно см. работу [10].
2) В лингвистически адекватной грамматике следовало бы порождать не
эти символы, а скорее более абстрактное представление предложения с ис-
использованием символов the, указат. местоимение, мн. число, tear, причастие,
book, мн. число, be, мн, число, complete, ly, worth, less (в указанном поряд-
порядке). Представление в терминах этих символов (называемых морфемами) мо-
может быть преобразовано в фонетическое представление с помощью фоноло-
фонологических правил, которые здесь не рассматриваются (см. Хомский и Мил-
Миллер [15]). Мы будем использовать предложения реального языка, типа B),
только для иллюстративных примеров н поэтому не будем заботиться о по-
подобных тонкостях.

198
//. Конский, М. Л^ Шютценберже
волов является, как и проблема эмпирической проверки аде-
адекватности некоторых категорий грамматик, ключевым пунктом
науки о языке, но она выходит за рамки данной работы.
Мы можем породить предложение "those torn books are
completely worthless" со структурным описанием B) с по-
помощью множества правил подстановки:
Пр. —* Гр. сущ. Гр. глаг.
Гр. сущ. —>¦ Дет. Прил. Сущ.
Дет. -* those
Прил. -* torn
Прил. -* worthless C)
Сущ. —» books
Гр. глаг. —> are Гр. прил.
Гр. прил. —> Нар. Прил.
Нар. —* completely
и вывода, который строится следующим способом: сначала пи-
пишем начальный символ Пр., который будет первой строкой вы-
вывода; (п-Н)-ю строку вывода образуем следующим образом:
выбираем произвольное вхождение нетерминального символа а
в я-ю строку (где а не является пометкой при скобке) и заме-
заменяем это вхождение цепочкой [aq>], где a—»q> — одно из пра-
правил C). Процесс продолжается до тех пор, пока из нетерми-
нетерминальных символов останутся лишь те, которые помечают скоб-
скобки. Тогда вывод будет закончен. Вычеркивая из законченного
вывода скобки с их пометками, мы получим цепочку, состоящую
только из терминальных символов. Назовем такую цепочку
терминальной. Грамматика C) порождает четыре различные
терминальные цепочки. Чтобы построить грамматику, поро-
порождающую бесконечное множество терминальных цепочек, ка-
каждую со структурным описанием, н,у,жно ввести рекурсию —
например, добавить к C) правила:
Гр. сущ. -* that Пр.
Гр. глаг. -* is Гр. прил. D)
Гр. прил. —> obvious.
При этом мы можем, например, породить цепочку "that
those torn books are completely worthless is obvious" и т. д. ')
') В этом случае можно породить бесконечное множество цепочек, не
?"Л?1О1!1НХСЯ предложениями английского языка, например «that those torn
!П\ ,is °bvious are completely worthless» и т, д, Следовательно, грамматика
и» неприемлема. Трудность избежать эмпирической неадекватности тв-
кого рода часто недооценивается. Еще раз подчеркнем, чго это ключевой во-
вопрос как для лингвистики, так и для психологин. Однако мы здесь этим
заниматься не будем. По этому поводу см. Хомскнй [13].
Алгебраическая теория контекстно-свободных языков
199
Каждое порождаемое предложение будет иметь структурное
описание подходящего вида.
Грамматики типа [C), DI мы будем называть контекстно-
свободными (кс) грамматиками1). Они характеризуются тем
свойством, что в левой части любого правила стоит лишь один
нетерминальный символ. Если это ограничение ослабить, можно
получить системы с совершенно другими формальными свой-
свойствами. Создается впечатление, что грамматика естественного
языка должна содержать по крайней мере несколько правил
подстановки этого более общего вида и несколько правил, ко-
которые вообще не являются правилами подстановки. Абстракт-
Абстрактное рассмотрение систем такого рода, которыми мы здесь за-
заниматься не будем, имеется в работах: Хомский [8], [10] и [12];
Хомский и Миллер [15]. Множество терминальных цепочек, ко-
которые могут быть порождены некоторой кс-грамматикой, будем
называть кс-языком.
Ке-грамматика может породить терминальную (освобожден-
(освобожденную от скобок) цепочку ф с несколькими разными структур-
структурными описаниями. Если грамматика эмпирически адекватна,
такая цепочка <р будет структурно неоднозначной. Рассмотрим,
например, кс-грамматику с правилами:
Пр. —¦ Гр. сущ. Гр. глаг.
Гр. сущ. —v they; Гр. сущ. -*Прил. Сущ.; Гр. сущ. -* Сущ.
Гр. глаг.—*are Гр. сущ.; Гр. глаг. -* Глаг. Гр. сущ.
Глаг. -* are flying
Прил. —> flying
Сущ. —¦ planes
E)
Эта грамматика может породить как F), так и G).
[Пр.[Гр. сущ. they] [Гр. глаг.[Глаг. are flying] [Гр. сущ.[Сущ.
planes]]]]. F)
[Пр.[Гр. сущ. they] [Г/?, глаг. are [Гр. сущ. [Прил. flying] [Сущ.
planes]]]]. G)
Соответственно терминальная цепочка „they are flying planes"
структурно неоднозначна; она может значить: "my friends, who
are pilots, are flying planes", или "those spots on the horizon
are flying planes". Изучение структурной неоднозначности —
один из наиболее поучительных путей определения эмпириче-
эмпирической адекватности грамматик.
') Соответствующий английский термин «context-free grammar (langua-
(language^ в других работах был переведен как бесконтекстная грамматика (язык).
См. Кибернетический сборник, № 2, 1966. — Прим. ред.

200
И. Хамский, М. П Шютценберже
Мы увидим ниже, что имеются кс-языки, которые ивляются
существенно неоднозначными в том смысле, что каждая кс-
грамматика, которая их порождает, обязательно приписывает
некоторым предложениям различные структурные описания.
Более того, мы увидим, что проблема распознавания по данной
кс-грамматике, является ли она неоднозначной, рекурсивно не-
неразрешима ') даже для"предельно простых типов кс-грамматик.
—Хотя кс-грамматики далеко недостаточны для естественных
языков, они, несомненно, адекватны для описания многих ис-
искусственных языков, в то"м числе для описания некоторых,
а возможно, и всех языков программирования. В частности,
может быть построена кс-грамматика для АЛГОЛа [18], при
этом каждая программа в АЛГОЛе будет одной из терминаль-
терминальных цепочек, порождаемых этой грамматикой. Очевидно, что
Яэнl^J^oгrJjJ^l^JjoRjЩИj^_Jraпж^н быть однозначным. Поэтому
для~конкретного языка программирования важно определить,
удовлетворяет ли он этому условию или, по крайней мере, мо-
может ли каждое конкретное бесконечное множество программ
быть однозначным, если задан некоторый метод для его по-
построения (например, метод, представимый с помощью правил
кс-грамматики). Как было отмечено в предыдущем абзаце, мо-
может оказаться довольно трудным ответить на этот вопрос.
Предположим, что Gt и G2 — порождающие системы, кото-
которые определяют некоторый метод для построения программ
для ЦВМ; допустим, что это грамматики, порождающие языки
программирования Li и L%, каждый из которых состоит из бес-
бесконечного числа цепочек (каждая_цепочка — возможная про-
программа). Часто бывает интересно исследовать относительную
силу языков программирования. Мы увидим, что если Oi и О2
есть кс-грамматики (как, например, в случае АЛГОЛа), то
большинство проблем, касающихся взаимоотношения между Li
и L2, рекурсивно неразрешимо. В частности, не решен вопрос
о том, будет ли пусто или бесконечно пересечение Li и Lz, ины-
иными^ словами, содержится ли Lx в L2 или существует ли конеч-
конечный преобразователь («компилятор»), отображающий Li на
L* (Гинзбург и Роуз, личные сообщения). Таким образом, воз-
возможно, что общие вопросы, касающиеся формальных свойств
кс-снстем и формальных отношений между ними, могут иметь
конкретную интерпретацию при изучении языков вычислитель-
вычислительных машин, а также при изучении естественных языков. На эту
} Другими словами, не существует механического процесса (алгоритма),
позволяющего для произвольной /сс-грамматики определить, приписывает ли
иекоторый порождаемый ею цепочке более одного структурного описа-
Алгебраическая теория контекстно-свободных языков
201
возможность указывали, в частности, Гинзбург и Райе [18],
Гинзбург и Роуз [19].
Рассматривая грамматику как порождающее устройство, мы
можем интересоваться языком (т. е. множеством терминальных
цепочек), который она порождает, или множеством порождае-
порождаемых ею структурных описаний [N.B.: каждое структурное опи-
описание однозначно определяет терминальную цепочку, как в B)].
Ясно, что последний вопрос более интересен. Аналогично при
изучении порождающей способности класса грамматик (или
относительной мощности нескольких таких классов, как бывает
при сопоставлении различных лингвистических теорий) нас мо-
может интересовать либо множество языков, либо множество
структурных описаний, которые эти грамматики могут поро-
порождать. Последний вопрос опять-таки более интересен, но и бо-
более сложен. Исследование таких вопросов началось, вообще
говоря, совсем недавно, причем внимание было сосредоточено
почти исключительно на порождении языков, а не систем струк-
структурных описаний. Мы будем рассматривать порождение как не-
нечто среднее между порождением языка и системы структурных
описаний, а именно мы будем рассматривать представление
языка не в виде множества цепочек и не в виде множества
структурных описаний, а в виде множества пар (ст, п), где
ст — цепочка, а п — степень неоднозначности, т. е. число различ-
различных структурных описаний, приписанных цепочке ст граммати-
грамматикой G, порождающей язык, которому принадлежит ст.
2. ГРАММАТИКИ КАК ГЕНЕРАТОРЫ ФОРМАЛЬНЫХ
СТЕПЕННЫХ РЯДОВ
2.1. Пусть дан конечный словарь V, разбитый на две части:
Vt (терминальный словарь) и VN (нетерминальный словарь).
Мы будем рассматривать языки над словарем Vt и грамма-
грамматики, нетерминальные символы которых берутся из VN. Пусть
F(VT)—свободная полугруппа, порожденная множеством VT,
т. е. множество всех цепочек а словаре Vt. Тогда каждый язык
есть подмножество множества F(VT).
. Рассмотрим отображение г, которое ставит в соответствие
каждой цепочке I(lF(Vt) некоторое целое число (г,/). Такое
отображение может быть представлено в виде формального
степенного ряда (обозначим его тоже через г) в некоммутатив-
некоммутативных переменных х из Vt- Таким образом,
г = 2 {г.!,) U =
г. h) h+{г. h) h+
(8)

202
И. Хомский, М. /7. Шютценберже
где /ь /г. • • • — пересчет всех цепочек в VT. Мы Определим опор-
опорное множество ряда г, обозначаемое Sup (r) как множество
цепочек, коэффициенты которых в г отличны от 0. Таким об-
ра30М
Sup (r)-{f,€F(VT)l{r, и)ФЩ. (9)
Мы не требуем, чтобы коэффициенты (г, ft) формального
степенного ряда г были положительными. Если для каждого i,
(f fi) ^ "¦ т0 мы будем говорить, что г — положительный фор-
формальный степенной ряд.
Если же для каждой ft?F(Vr) коэффициент (/¦,/<) равен 0
или 1, мы будем называть г характеристическим формальным
степенным рядом своего опорного множества.
2.2. Если г — формальный степенной ряд ил — целое число,
будем определять произведение пг как формальный степенной
ряд с коэффициентами (nr,f)=n(r,f), где (г, ft — коэффи-
коэффициент / в ряде г. Если г и г' — формальные степенные ряды,
определим r+г' как формальный степенной ряд с коэффициен-
коэффициентами (г+г', /} = (/-, /)+</', ft, где (г, ft и </¦', ft—соответ-
ft—соответственно коэффициенты / в г и в г'. Определим гг' как формаль-
формальный степенной ряд с коэффициентами {rr', !)=2i{rJi){r',fj),rRe
fift=f. Таким образом, множество формальных степенных рядов
образует кольцо, замкнутое относительно операций умножения
на число, сложения и умножения.
Заметим, что если г я г' — положительные формальные сте-
степенные ряды, то опорное множество ряда r + г' будет равно
эбъединению опорных множеств рядов г и г', а опорное множе-
:тво ряда гг'— прямому произведению опорных множеств ря-
рядов г и г' (т. е. множеству всех цепочек ltfjt таких, что /<
принадлежит опорному множеству ряда г, a fj — опорному мно-
«еству ряда /¦'). Ниже мы рассмотрим интерпретацию некото-
некоторых других простых теоретико-множественных операций.
Будем называть два формальных степенных ряда г я г' эк-
швалентными по модулю степени п (/¦=/•'(mod deg п)), если
'г> /) = ('¦', /) для каждой цепочки / длины («степени») < п.
федположим, что имеется бесконечная последовательность
рормальных степенных рядов г,, гг, ..., такая, что для ка-
кдого п и для каждого п'>п, /V ^л„ (mod deg я). В таком слу-
1ае пРеДел последовательности ги г2, ... вполне определяется
'авенством
г = lim л„г„,
A0)
" сражение л„гп есть полином, образован-
заменой на нули всех коэффициентов при цепочках
Алгебраическая теория контекстно-свободных языков
203
длины больше п. Тогда кольцо формальных степенных рядов
становится ультраметрическим, а следовательно, топологиче-
топологическим кольцом.
Сформулировав эти определения, мы можем обратиться
к проблеме взаимоотношения между представлением языков
в терминах формальных степенных рядов и представлением
Языков с помощью порождающих процессов (таких, как кс-
грамматики).
2.3. Предположим, что G—процесс, порождающий язык
L(G). Каждой цепочке f€F(Vr) приписывается некоторое чис-
число N(G,f) структурных описаний в G; N(G, ft >0 в точности
в том случае, когда f(iL(G).*N(G, ft выражает степень струк-
структурной неоднозначности / по отношению к грамматике G. Есте-
Естественно ассоциировать с G формальный степенной ряд r(G),
такой, что {r(G), f)—N(G, f), где (/(G), ft —коэффициент при
цепочке / в r(G). Таким образом, r(G) выражает неоднознач-
неоднозначность всех терминальных цепочек по отношению к грамма-
грамматике G. Коэффициент {r(G), ft равен нулю в точности в том
случае, когда / не порождается грамматикой G, и единице, если
/ порождается однозначно (одним и только одним способом)
грамматикой G; он равен двум в точности в случае, когда
имеются два различных структурных описания для f в грамма-
грамматике G, и т. д.
Ряд r(G), ассоциируемый с грамматикой G, разумеется,
всегда положителен, и его опорное множество Sup (r(G)) есть
не что иное, как язык L(G), порождаемый грамматикой G. Мы
можем далее считать, что формальный степенной ряд г, имею-
имеющий как положительные, так и отрицательные коэффициенты^
ассоциируется с двумя порождающими процессами Gi и G2.'
Коэффициент {г, ft цепочки f в г можно при этом рассматри-
рассматривать как разность между числами способов, которыми / поро-
порождается в Gi и в G2, т. е.
{г, f)=N(Gu f)-N(G2, ft.
Предположим, что G есть кс-граммятикя с нртррминяпь-
ными символами Gti, ..., ап, где af есть отмеченный начальный
символ [в примере A) Пр. =aj. Мы можем построить фор-
формальный степенной ряд r(G), ассоциируемый с G прямой ите-
итеративной процедурой. Сделаем это следующим образом.
Во-первых, G может быть записана как система уравнений
от переменных аи . ._LL_an. Пусть <m. i qu mt—цепочки та-
кие, что <Х(—npi, j (I 4j/-Cmj) суть правила грамматики G.
Сопоставим переменной аа полиномиальное выражение di,
i, 2+ .. • +q><, m(- A1)

204
Н. Хомский, М. П. Шютценберже
Тогда грамматике ставится в соответствие множество урав-
неняй
а1 = ст1, .... сс„ = (Тп. A2)
Предположим, что грамматика G не содержит правил типа1)
aj->aj. A3)
Ясно, что эги предположения не изменяют порождающей
способности [2]. Это означает, чуо для каждой кс-грамматики,
содержащей такие правила, существует"другая~пзамматика без
таких правил^сог^^1?^^)ождает_гдт же язык. С настоящего
момента мьГбудем также трёТхжать, чтобы, какова бы ни была
кс-грамматика б, для любого ее нетерминального символа а
существовала терминальная цепочка, выводимая из а; это озна-
означает, другими словами, что если рассмотреть грамматику G',
содержащую правила вн j как начальный символ, то язык,
порождаемый G'(L(G')), должен быть не пустым. Это требо-
требование также, очевидно, не влияет на порождающую способ-
способность.
Возвращаясь теперь к проблеме построения степенных ря-
рядов, ассоциируемых с грамматикой G и представляющих сте-
степень неоднозначности, которую G приписывает каждой цепочке,
заметим, что мы можем рассматривать каждое уравнение а,- =
= tfj из A2) как определение отображения %, которое перево-
переводит я-ку степенных рядов (ги ..., гп) в степенной ряд, полу-
полученный заменой ocj в <л на /> Это можно делать ввиду свойств
замкнутости кольца степенных рядов, указанных в разд. 2.2.
Таким образом, множество уравнений A2) определяет ото-
отображение Г|),
¦ (г„ .... /¦„) = (/¦; г'п), где /¦{*=¦,(г, гп). A4)
Рассмотрим теперь бесконечную последовательность я-
степенных рядов р0, pi, ..., где
ок
ft = (ro,i /•о,л) = (О, •••• 0),
Р: = (г,,„ ..., /",,„),
Р2 = (г2|1, ¦• ., г2_а)
« — пустая цепочка. — Прим. перед.
A5)
Алгебраическая теория контекстно-свободных языков
205
и где для любых i, j (/>0)
••> O-l, n)
A6)
и 0 означает степенной ряд, у которого все коэффициенты есть
нули. Каждый ряд Г),{ в A5) имеет только конечное число не-
ненулевых коэффициентов, другими словами, rj, j — полином. Бо-
Более того, можно показать, что для любых i, j, j', таких, что
/'>/>0, 1 ^Ci^Cn, имеет место
О, <=Г/М (moddeg/).
A7)
Следовательно, как замечено в разд. 2.2, предел г«,^ беско-
бесконечной последовательности п, j, r2| j, • ¦ ¦ вполне определен для
каждого ( (вообще говоря, он, конечно, не является полино-
полиномом). Назовем я-ку (г„о, и ..., г», п), определенную таким об-
образом, решениём~сшстемъГуравнений A2). В самом деле, я-ка
(лСО|! /¦«,,„)¦—единственная я-ка, удовлетворяющая си-
системе уравнений A2). Поэтому мы будем говорить, что степен-
степенной^ ряд является алгебраическим [42], если он входит в я-ку,
являющуюся ррщрнирм нркотпрпй системы уравнений „вида
A2), без ограничений на знаки коэффициентов. Назовем сте-
степенной ряд контекстно-свободным, если все коэффициенты
в определяющих уравнениях положительны.
В частности, ряд л», ь который мы будем называть степен-
степенным рядом, порождаемым грамматикой G [определяющей си-
систему A2) и имеющей в качестве начального символа aj, есть
степенной ряд, ассоциируемый с грамматикой G, как это опи-
описано в начале разд. 2.3. Опорное множество ряда л», i есть
язык L(G), порождаемый грамматикой G, и коэффициент
(г=о>ь f) ПРИ цепочке f€.F(VT) определяет неоднозначность /
по отношению к G (способом, описанным выше).
Заметим, что если алгебраический степенной ряд является
контекстно-свободным, то он положителен, но обратное не все-
.гда верно — степенной ряд может быть членом решения си-
системы уравнений и иметь только положительные коэффициенты,
но в то же время может не быть членом решения никакой си-
системы уравнений, имеющих только положительные коэффи-
коэффициенты ').
') Например, мы здесь используем понятия, которые будут определены
ниже, в разд. 3.1. Адамаровский квадрат sOs, для s (j Xo, имеет только по-
положительные коэффициенты (н имеет то же самое опорное множество, что
и 5), но не порождается, вообще говоря, системой уравнений с положитель-
положительными коэффициентами.

206
Н. Хамский, М. П. Шютценберже
2.4. В качестве примеров описанного выше процесса рассмо-
рассмотрим две грамматики A8) и A9):
S-*bSS; S-*a, A8)
S^-SbS; S — a. A9)
Каждая нз этих грамматик имеет единственный нетерминаль-
нетерминальный символ, а, следовательно, соответствующая ей система урав-
уравнений будет состоять из одного уравнения. Грамматике A8) со-
соответствует уравнение. B0), а грамматике A9) уравнение B1):
B0)
S^a + SbS. B1)
Уравнения B0) и B1) соответствуют системе A2) (см. выше)
с п=1; как B0), так и B1) удовлетворяют условию A3).
Рассмотрим сначала грамматику A8), представленную
в форме B0). Действуя, как в предыдущем разделе, мы будем
считать, что B0) определяет отображение i|>, такое, что -ф(г) =
*=a + brr, где г — степенной ряд. Затем [аналогично A5)] по-
построим бесконечную последовательность р0, pi, рг, ... следую-
следующим образом:
Ро = гп — О,
р: = Г\ = a -f- brnr0 = а-\- ЬОО = а.
Рг = r2 = a -f- brxrx = а + baa,
Рз = л3 = a -f br2r2 = a-j~b(a-\- baa) (a + baa) = B2)
= a -)- baa + babaa -\~ bbaaa -f bbaabaa,
Очевидно, что для любых /, /", таких, что /'>/>0, будет
иметь место г,=лу (niod cleg/). Следовательно, предел /•«, вполне
определен. Этот степенной ряд есть решение уравнения B0) и
его опорное множество является яаыком. порожденным кс-
Щаммагикой A8). Заметим, что степенной ряд г«, является ха-
характеристическим и его опорное множество есть множество
правильно построенных формул «исчисления импликаций» с од-
одной переменной в бесскобочной (польской) системе обозначе-
обозначений. (Здесь а есть пропозициональная переменная, ab — опера-
оператор импликации.)
Теперь рассмотрим грамматику A9), представленную в фор-
ме B1). B1) определяет отображение г|), такое, что 1|)(л) =
"a + rbr, где г — степенной ряд. Построим теперь бесконечную
Алгебраическая teQpusi контекстно-свободных языков
207
последовательность ро, pi, рг, .. .:
Ро = '"о = 0.
Pj = ri = а + robro = a-\- 0*0 = а,
р2 = г2 = а -\- гфгх =.а-\- aba,
Рз = гз = «¦+ r2br2 = a-\-(a + aba)b(a-\- aba) =
= а -\- aba -\- 2ababa ¦+ abababa,
р4 = r4 = а + гфгг = а + aba -\- a (abf а -\-
+ 5 (abf а ¦+ 6 (л*L а + 6 (а*M а +- 4 (а*N л + (abOa.
B3)
Для любых у и /, таких, что у">у>0, имеет место Гу=
^r'(mod degy) и предел г^ определяется как степенной ряд
+ 5 (abf a+U (abf а + 42 (а*M а +
B4)
где
2n X 2n — 1 X ¦¦¦ X " + '
1 X2X ... X»
Степенной ряд г» [из B4I есть решение уравнения B1); его
опорное множество — язык, порождаемый грамматикой A9).
Здесь ряд не является характеристическим. Если рассматривать
символ а как пропозициональную переменную, а Ь — как знак
для оператора импликации, то грамматика A9) представляет
собой множество правил для порождения правильно построен-
построенных формул исчисления импликаций с одной переменной в обыч-
обычной системе обозначения, но с опущенными скобками. Струк-
Структурные описания, порождаемые грамматикой A9) (как описано
в разд. 1), являются, конечно, однозначными, пока сохраняются
скобки, но терминальные цепочки, полученные отбрасыванием
скобок, будут неоднозначными и степень неоднозначности для
каждой порожденной цепочки есть не что иное, как ее коэф-
коэффициент в ряде г«,; так, ababa может интерпретироваться или
как (ab(aba)), или как ((aba)ba) и т. д. Более общий случай
был рассмотрен Ранеем [38] с помощью формулы обращения
Лагранжа.
В уравнениях B0) и B1) все коэффициенты положительны
и решение, следовательно, является положительным степенным
рядом. Рассмотрим теперь систему, состоящую из одного урав-

Н. Конский, М. П. Шютиенберже
нення
S = а — SbS.
Тогда получается последовательность
р, = г, = а — /•„*/•„ = а — 0*0 = а,
Рг = Г2 = « — r\bri = а — ate,
B,5)
= а — ate -j- lababa — abababa.
B6)
Коэффициенты Pi в B6) совпадают с точностью до знаков
с коэффициентами ряда р, в B3), причем коэффициенты ряда р<
при цепочке / в B6) положительны, если / содержит четное
число вхождений Ь.
Степенной ряд г», являющийся решением системы B5) не
является положительным, а следовательно, и контекстно-сво-
контекстно-свободным [хотя его опорное множество и является контекстно-
свободным языком, причем A9) может быть рассмотрена как
одна из его грамматик]. Однако мы можем рассматривать /¦„
как разность между двумя контекстно-свободными рядами
га> и г» и соответственно его опорное множество рассматри-
рассматривать как множество цепочек, которые не порождаются одина-
одинаковое число раз парой кс-грамматик G* и G; порождающих
соответственно г+ н /•-. Предположим, что S=S*~S', так что
B5) можно записать как
= a-E+ -S')b(S+ -5") =
Рассмотрим теперь систему уравнений B8)
(i) S+=
(ii) 5- =
B7)
B8)
СиСТема B8) является системой положительных уравнений
с Двумя переменными S* и S-. Эта система будет иметь реше-
решением пару (г+. г-), где г? есть предел последовательности
Алгебраическая теория контекстно-свободных языков
209
г+, г{, . .., а г^— предел последовательности г~, г~, ... из B9):
Ро = (^. 'о-) = @.0).
Р1 = (''.1. T) = (a,0), B9)
р2 ==(/• + , r-) = (a, «to).
Ясно, что если /•» есть решение системы B5), то гш = г^—
— га. Но, более того, г^ — это степенной ряд, порожденный
грамматикой G* и начальным символом S+ [этой грамматике
соответствует уравнение (i) из B8)]; г^ — это степенной ряд,
порожденный грамматикой G~ и начальным символом S~ [этой
грамматике соответствует уравнение (ii) из B8)].
Подобным образом каждый алгебраический степенной ряд
может быть представлен (бесконечным числом способов) в виде
разности двух контекстно-свободных степенных рядов, и его
опорное множество можно рассматривать, следовательно, как
множество цепочек, которые не порождаются одинаковое чис-
число раз двумя кс-грамматиками. Рассуждения в общем слу-
случае настолько сходны с приведенными, что мы можем перейти
к конкретной интерпретации общего понятия алгебраического
степенного ряда.
Ту же конструкцию можно было бы применить к произволь-
произвольному кольцу коэффициентов вместо кольца натуральных чисел,
использованного выше. Это еще не исследованная область. На-
Например, если брать коэффициенты по простому модулю р (т. е.
если рассматривать как «непорождаемые» те цепочки, число
случаев порождения которых кратно р), то формальный степен-
степенной ряд 2 г? с единственным терминальным символом г яв-
л >0
ляется алгебраическим [27], хотя его опорное множество не мо-
может быть опорным множеством никакого степенного ряда рас-
рассмотренного выше типа.
3. ДРУГИЕ ОПЕРАЦИИ НАД ФОРМАЛЬНЫМИ
СТЕПЕННЫМИ РЯДАМИ
3.1. В разд. 2.2 мы заметили, что множество степенных ря-
рядов замкнуто относительно операций сложения, умножения и
умножения на целое число. Мы указали также, что опорное
множество ряда r + г' есть объединение опорных множеств ря-
рядов гиг'и что опорное множество ряда гг' есть произведение
опорных множеств г и г', при условии, что коэффициенты не-
неотрицательны. Теперь мы рассмотрим две другие операции, от-
относительно которых множество степенных рядов замкнуто, и
14 Зак. 243

210
Н Хамский, М. П. Шютценберже
рассмотрим соответствующую теоретико-множественную интер-
интерпретацию для опорных множеств.
Будем, как обычно делается, называть ряд квазирегулярным,
если <г, е>=0. Тогда г"' ==0(moddeg«) для 0 < п < п' и
"' вполне определен. Более того,
элемент г* = lim 2и Г
Л->0О 0 < П' < П
ряд г* удовлетворяет тождеству
г + rV = г + /т* = г*,
C0)
которое определяет его однозначно. При этом ряд г* обычно
называется квазиобратным для г. Это понятие непосредственно
связано с более известным понятием обратного элемента. Имен-
Именно если г' = е— г и г" = е + г*, то г'г"= (е — г) (е + r*) =е — г-\-
+ г* — rr* = e — r"r', иными словами, г"=г'~х. Обратно, если дан
ряд г' такой, что </¦', е> =1, то можно его записать как
г' = е— г, где г — квазирегулярвый, и тогда е + r* есть ряд, об-
обратный для г'.
Заметим, что из определения ряда г* следует, что он имеет
неотрицательные коэффициенты, если этим свойством обладает
ряд г, и что справедливо равенство Sup r*— (Sup r)*, где звез-
звездочка в правой части равенства означает операцию итерации
Клини [21].
В частности, если V—произвольное множество букв и сте-
степенной ряд v определен следующими условиями: <У, х> =1,
если x?V, и <о, х> =0, если x(?V, иными словами, если v
является характеристической функцией V, то e+V* (в смысле
Клини) есть множество всех слов, порожденных элементами
V, a e + v*=(e — о)~> есть характеристическая функция этого
множества. Это следует из того, что каждое слово /6V* встре-
встречается один и только один раз в бесконечной сумме вида
2 V". Следовательно, если мы знаем характеристическую
функцию г множества цепочек, то мы можем также написать-
характеристическую функцию A — Vt)'1 — г его дополнения.
Стоит заметить, что в этом случае последний ряд имеет не-
неотрицательные коэффициенты и, хотя он алгебраический в опи-
описанном выше смысле, он не обязательно является контекстно-
свободным.
Вторая операция, которую мы определим, — это адамаров-
ское произведение. Таким образом, мы обобщим еще одно по-
иятие~классического анализа. Определение, которое мы дадим,
отличается от принятых в литературе обобщений на случай не-
нескольких переменных, но нам оно кажется более естественным
для случая некоммутативных степенных рядов.
Алгебраическая теория контекстно-свободных языков 211
Если гиг' — степенные ряды, то их адамаровским произ-
произведением будет степенной ряд г © г' с коэффициентами
(rQr',!) = {r,!){r',f) C1)
для всех цепочек /. Следовательно, Sup (rQr') = (Sup r) fl
n(Supr'), и если г и г' — характеристические функции, то
rQr' — тоже характеристическая функция.
Наконец, введем следующее обозначение: имея цепочку
Xt1Xi1 ¦ ¦. Xtn_ixtit = f {Xi,6 V), определим { (зеркальный об-
образ f) как цепочку
f=-w, •¦• -"w C2)
Ясно, что / = f и что равенство ff' — f" влечет равенство
f"=f'f. С формальной точки зрения это отображение является
инволютивным антиавтоморфизмом кольца степенных рядов.
Можно показать, что оно однозначно определяется этим свой-
свойством (с точностью до перестановки элементов из V).
3.2. Только что введенные обозначения будут в дальнейшем
применяться для упрощения описания грамматик следующим
образом. Предположим, что грамматика G содержит следующие
правила:
щ = n^jrtj + я,я2 ¦+ Щ,
а2 = а2я4-|-1Т4.
где Я) — полиномиальное выражение над V — {d}- Тогда вто-
второе правило влечет
o, = (Snj) C4)
и правила C3) могут быть заменены более простыми прави-
правилами
а, = 1г,A—я4)
C5)
Этой упрощенной форме описания можно дать лингвистиче-
лингвистическую интерпретацию. Так, например, мы можем считать, что
пара правил вида а( —»/i«2f2 и а2 — «гаг [эту пару теперь можно
представить в форме <Ч—>/iO—а2) '/г] является фактически
схемой правил: a,->f,aJ/2 (я = 1, 2, ...). При такой реинтер-
претации грамматика (хотя схема правил определяет ее фи-
финитно) имеет бесконечное число правил. Теперь вспомним ме-
метод, с помощью которого терминальной цепочке, порождаемой
кс-грамматикой, приписывалось структурное описание (с поме-
помеченными скобками, см. выше разд. 1). Грамматика, определен-
определенная данной выше схемой правил, может порождать структур-
14*

212
//. Хомский, М. 17. Шютценберже
ное описание вида
¦ ¦ • Kfi[02P1]Кл1 ¦ ¦ ¦ [<ВД>]h] ¦¦¦ C6)
для любого п, где каждое pi, выводимо из о.ъ В предложении
(терминальной цепочке) с таким структурным описанием ка-
каждое ph есть словосочетание типа а2 (рк получается стиранием
скобок в ph)- Словосочетания pi pn образуют «сочинитель-
«сочинительную конструкцию», которая, рассматриваемая вместе с цепоч-
цепочками, образованными в конечном счете из ft и /2, является кон-
конструкцией типа at. Это естественный способ расширить кс-грам-
матикн с тем, чтобы онн могли описывать сочинительные кон-
конструкции (например, цепочка прилагательных произвольной
длины, не несущая внутренней структуры, может встречаться в
позиции именной части сказуемого (см. Хомский [10])).
3.3. Попытаемся связать то, что мы до сих пор делали, с
классическим анализом. Будем писать ф/ = фГ для любых двух
цепочек / н /', если они содержат одинаковое число вхождений
каждого символа (терминального нли нет).
Ясно, что ф распространяется до отображения наших не-
некоммутативных степенных рядов на кольцо произвольных (ком-
(коммутативных) формальных степенных рядов с целыми коэффи-
коэффициентами. Легко видеть, что ф — гомоморфизм. Например, если
а — а+Ьаа, то фа*=фа+ф&фафа, а фа — обыкновенный степен-
степенной ряд
Я» = (фв)"+1(Ч*)"[2,Г]-г4т О?)
с переменными фа и фй (если а' = а + а'Ьа', то фа' = фа).
Более того, из способа, которым были получены наши сте-
степенные ряды, можно было бы вывести, что коэффициенты ряда
растут не быстрее, чем экспоненциальная функция степени (дли-
(длина) цепочек. Так, образ ф любого из наших степенных рядов
есть конечный сходящийся ряд Тейлора, являющийся разло-
разложением некоторой алгебраической функции.
Обратно, если даны (обычные) переменные xj хп, то
(обычная) алгебраическая функция от « переменных у опре-
определена полиномом, зависящим от у и х\-; и в случае, если у до-
допускает разложение в ряд Тейлора (с целыми коэффициентами)
в окружности нуля, мы можем ассоциировать с ней бесконечно
много формальных степенных рядов р, таких, что фВ = |/ и р оп-
определяет™ формальными уравнениями. Например, исходя из
ской функции от аргументов а и Ь, определенной
.... угЪ — у + а^О, мы получим два вышеприведенных
примера, а также формальный степенной ряд
— ал, C8)
Алгебраическая теория контекстно-свободных языков
213
где я есть произвольный полином от а и Ь. Положим, напри-
например, я = 6. Тогда
щ = а + baa -j-ba — ab
C9)
и т. д.
3.4. В заключение укажем на некоторые связи между на-
нашими рассмотрениями и линдоновской теорией уравнений в сво-
свободной группе (Линдон, 1960). Пусть [xt] (\^i<Cn) есть тер-
терминальный словарь, ? есть нетерминальный символ, и пусть w
есть произведение членов вида 1—хи A—Xt)'1, 1—|,
A—|)-'. Положим deg (w)=d+— d-, где d+ и d- — соответ-
соответственное число сомножителей в 1 —| и A —|)"' в w. Так, на-
например, для ш=A— хг) (\ - Xi) (\ — S)(l— *()¦'(!— Si) X
X A —х2)~1 имеем deg(av) = l — 1=0.
Как хорошо известно, элементы 1 — xt порождают (по ум-
умножению) свободную группу G. Равенство w — \ можно рассма-
рассматривать как уравнение с неизвестным \. В нашей терминологии
решением уравнения ш=1 будет степенной ряд So от перемен-
переменных *,-; причем ш=1 тождественно, если в w вместо S подста-
подставить 10; So будет групповым решением, если, кроме того,
1 — |о€ G, т. е. если 1 —10 само может быть представлено как
произведение членов A—х{)±1. Линдон получил следующий
замечательный результат: совокупность групповых решений мо-
может быть получена алгоритмически.
Этот вопрос частично связан с замечаниями, сделанными в
разд. 2.3. Введем новые символы |(A^/^п), ц и уравнения
Ъ, = х, + 1,х« i/ = |2 + Sri. (!)
так что A—JCj)~1 = l+ii и A— i)-' = l+i+S2 + Sn.
Подставляя эти выражения в уравнение w—\ и упрощая
его, получим равенство
р', B)
где р' есть полином от переменных *,-, S«. Л. не содержащий чле-
членов степени ниже 2.
Сл^овательно, если deg(w)фO, то система A), B) имеет
одно и только одно решение в степенных рядах (то, что коэф-
коэффициенты могут быть здесь не целыми, а рациональными чис-
числами, не влияет на доказательство, приведенное в разд. 2.3);
поскольку групповые решения образуют подмножество множе-
множества решений в степенных рядах, мы непосредственно убеж-
15 Зак 213

214
Н. Хомский, М. П. Шютценберже
даемся, что если deg (ш) =?0, то уравнение в свободной группе
ш = 1 имеет самое большее одно решение.
Если же deg(aj)=O (как, например, для уравнения
да=A — ?)(' — *0О — 1)"'(! — х{)-'=\), то наш подход не по-
позволяет вообще ничего сказать о решении уравнения ш=1.
Например, уравнение A — х{) A — Q A — х()'A —1)-' = 1
не имеет решений, если е?= — 1, и имеет бесконечно много «pt/n-
повых решений, если е= — 1, а именно 1—1=A—**)±п
(я>0). Действительно, тогда уравнение эквивалентным обра-
образом может быть записано в виде |л:1=^|. Решениями этого
уравнения в нашем смысле являются все степенные ряды от
переменного Xi.
Конечно, случай deg(w)—0 имеет место именно тогда, когда
неизвестное 1 — ? исчезает при взятии коммутативного образа
(см. разд. 3.3). Этот случай нетривиален с точки зрения теории
групп.
4. ТИПЫ АТС-ГРАММАТИК И СВОЙСТВА ПОРОЖДАЕМЫХ
ИМИ ЯЗЫКОВ
4.1. Мы можем определить несколько особо интересных ка-
категорий кс-грамматик, накладывая условия на входящие в них
правила. В дальнейшем будем употреблять буквы а, р,... для
обозначения нетерминальных символов, буквы /, g,... для тер-
терминальных цепочек (возможно пустых) и ф, \р — для произволь-
произвольных цепочек. Напомним, что мы исключили правила вида а-*е
и а -»р, причем это не влияет на порождающую способность
грамматик. Мы будем описывать кс-грамматики в терминах
правил или^равнений^ смотря по тому, как нам будет удобнее.
Если грамматика и Те содержит нетерминального символа а,
из которого можно вывести как цепочку /', так и цепочку fagK
то терминальный язык L(G), порождаемый грамматикой G, бу-
будет конечным. В этом случае грамматика G будет называться
полиномиальной грамматикой. Рассмотрим теперь грамматиче-
грамматические правила следующих видов:
1)а->/р (правостороннее),
2) а-*р/ (левостороннее),
3) a^-fpg (линейное), ^ '
4) a->f (заключительное). •
Грамматика, содержащая только правосторонние н заклю-
заключительные правила или только левосторонние и заключитель-
заключительные, будет называться односторонней линейной грамматикой.
Алгебраическая теория контекстно-свободных языков
215
Грамматика, содержащая только правила типа D0), будет
называться линейной. Предположим, что грамматика G содер-
содержит правила только типа D0) и правила типа а4 —* ф, где
cci — начальный символ грамматики G, и что, кроме того, она
не содержит правил вида р—«-фа^. Тогда определяющее урав-
уравнение для ccj есть сс! = Я1, где щ — полином, не содержащий oti.
Такая грамматика будет называться металинейной.
Если грамматика G (т. е. система уравнений с положитель-
положительными коэффициентами) является полиномиальной, односторон-
односторонней линейной, линейной, металинейной или контекстно-свобод-
контекстно-свободной, будем называть степенной ряд г, являющийся главным чле-
членом ее решения (т. е. тот ряд, который она порождает, в
смысле, определенном в разд. 2.3), и языки Sup p соответствен-
соответственно полиномиальными, односторонними линейными, линейными,
металинейными или контекстно-свободными. Эти семейства сте-
степенных рядов будут обозначаться соответственно S°+, 3"t* J?+•
¦3"т, 3 + > и для каждого семейства <&~ семейство опорных
множеств будет обозначаться Sup(^).
Заметим, что Sup(i^+) есть семейство конечных множеств,
a Sup(^"^)—семейство регулярных событий Клини [21] (см.
Хомский [7]). Заметим, что класс регулярных событий замкнут
относительно отражения.
Рассмотрим некоторые элементарные свойства этих семейств
языков.
Очевидно, прежде всего, что
Sup(^+) с SupC^tf) с Sup(^"+) с Sup(^+) с Sup(#+). D1)
Более того, в каждом из этих случаев включение является
собственным. Таким образом, мы имеем
Свойство 1.
Sup (^+) % Sup (.gtf) ф Sup (^+) J Sup (^) ^ Sup {g +).
Простейшим примером языка, принадлежащего Sup(^4), но
не Sup (j?oO, является множество всех цепочек вида
{anban) (а, 66 Уг). Оно порождается грамматикой вида
~d = aaa + b. Легко показать, что этот язык не является регуляр-
1шм собТатием. Произведение языков из Sup(^>+) всегда при-
11адлёжит Sup (j?m), но не обязательно принадлежит Sup(J?"+).
Язык Lie из нашего примера A8), имеющий грамматику
D2)
и представляющий собой множество правильно построенных
формул исчисления импликаций с одной свободной переменной
15'

216
Н. Хомский, М. П. Шютценберже
в польской системе обозначения, принадлежит Sup(^7+), но не
Sup (-?«)• Это следует из того, что язык Lie содержит все це-
цепочки вида
bm>amibm*am= ... bm*am*a, D3)
для каждого ?> 1, т,'> 1. Но каждая цепочка языка LIC со-
содержит п вхождений Ь и п+\ вхождение а для некоторого
я > 1. Следовательно, для фиксированного целого числа k, для
того чтобы породить все цепочки вида D3), нужно иметь воз-
возможность вывести из начального символа грамматики LIC це-
цепочку ф, содержащую k вхождений нетерминальных символов.
Следовательно, эта грамматика не может быть металинейной.
Для содержательной интерпретации теории кс-грамматик
особое значение имеет отношение между Sup(^7+) и Sup(j?"o+),
потому что конечное устройство, включающее в себя некоторую
кс-грамматику G, порождающую язык L(G), может анализиро-
анализировать предложение только из фиксированного подмножества
,/??Sup (j?oO языка L{G) 6 Sup lff+) (при фиксированных до-
дополнительных средствах). Это отношение может быть точно
описано в терминах некоторых формальных черт структурных
описаний (с помеченными скобками), порождаемых кс-грамма-
тиками (см. разд. 1). Будем говорить, что грамматика G есть
грамматика с самовставлением, если она порождает некоторое
структурное описание вида
оф] х]
D4)
где ф и х содержат терминальные символы, а ф есть выражение
с правильно расставленными скобками. Тогда имеет место сле-
следующий результат.
Теорема la. L^S't тогда и только тогда, когда каждая
кс-грамматика, порождающая L, есть грамматика с самовстав-
лением (Хомский [9]).
OmfT°T результат может быть обобщен следующим образом,
какГ ™ степень самовставления структурного описания D
[оЫе!ы г166 Ni Такое> чт0 D содеРжит подконфигурацию
мин!шС ''' '¦axfH+1WN+z]... ]ф2№-ц], где каждое <р, содержит тер-
тивнп! *СИМВОЛЫ- Тогда существует одно-однозначное эффек-
эффектна я >°пРажеНие Ф множества пар {(G, п) : G кс-грамма-
и олип В0 множество односторонних линейных грамматик
TpvKTvn означное эффективное отображение Ч множества Д
ей тео °ПИСаний в себя- такие- qT0 они описываются сле-
Алгебраическая теория контекстно-свободных языков
217
Теорема 16. Для каждого L^Sup(^7+) существует кс-
грамматика G, порождающая L, такая, что для каждого N
<D(G, N) порождает цепочку f со структурным описанием D
тогда и только тогда, когда G порождает терминальную це-
цепочку f со структурным описанием Чг(?>), где ^(D) имеет сте-
степень самовставления ¦< N (Хомский [8]).
Таким образом, мы можем интуитивно, имея G, построить
конечное устройство O(G, N), которое будет распознавать
структуру цепочки f, порождаемой грамматикой G, в точности
тогда, когда степень самовставления данного структурного опи-
описания f не превышает N. Отсюда вытекают некоторые содер-
содержательные следствия (см. Хомский [10], Миллер и Хомский
[29]).
4.2. Рассмотрим некоторые свойства замкнутости данных се-
семейств языков.
Семействам степенных рядов, определенных выше, может
быть дана следующая алгебраическая характеристика. &>+ есть
полукольцо1). J?o —наименьшее полукольцо, содержащее if*
и замкнутое относительно квазиобращения квазирегулярных
элементов. J?"+ есть модуль, a -iPra есть наименьшее полукольцо,
его содержащее. Полное множество 0+ есть полукольцо, замк-
замкнутое относительно квазиобращения квазирегулярных элемен-
элементов.
Соответственно мы имеем следующие свойства опорных мно-
множеств: Sup(i^) замкнуто относительно теоретико-множествен-
теоретико-множественного объединения н прямого умножения; Sup(-2'o~) есть наи-
наименьшее множество, содержащее конечные множества и замк-
замкнутое относительно теоретико-множественного объединения,
прямого умножения и итерации, описанной в разд. 3.1 [21];
Sup(J?"+) замкнуто относительно теоретико-множественного
объединения, но не прямого умножения; Sup(^i) есть наи-
наименьшее множество, содержащее множества из Sup(J?+) и
замкнутое относительно прямого умножения (введение J?m
было обусловлено, конечно, не этими соображениями); Sup(^ + )
замкнуто относительно объединения произведения и итерации.
Эти свойства очевидны; естественно возникает вопрос о замк-
') Поннтне полукольца обобщает понятие кольца таким образом, что в
качестве его аддитивной структуры допускается полугруппа (не обязатель-
обязательно группа).
Пример полукольца — так называемое «булевское кольцо» с двумя эле-
элементами 0 и 1 и правилами
@-0 + 0 = 00 = 01 = 10; 1 = 0+1-1 + 0=1 + 1 = 11).

218
Н, Хомский, М. П. Шютценберже
вутости относительно других элементарных операций над мно-
множествами, а именно пересечения и дополнения.
Очевидно, что Sup(^+) замкнуто относительно пересечения;
хорошо известно, что класс Sup(^0+) регулярных событий замк-
замкнут относительно пересечения и дополнения.
Для остальных множеств имеем следующие результаты
Множество Sup(#+) всех кс-языков не замкнуто относительно
пересечения и, следовательно (так как оно замкнуто относи-
относительно объединения), не замкнуто относительно дополнения [40]
[2]. Пример, приведенный в обеих работах, представляет собой
пару металинеиных языков '), пересечение которых не является
кс-языком. Следовательно, Sup (_?¦+) тоже не замкнуто отно-
относительно пересечения и дополнения. Этот результат может быть
распространен на линейные грамматики н даже (для пересече-
пересечения) на линейную грамматику с одним нетерминальным сим-
символом.
Чтобы показать это, рассмотрим грамматики G, и G2 опре-
определенные соответственно следующими выражениями:
а = ааас -f- bac -4- be,
а = аасс + aab + ab.
D5)
D6)
Gi и G2 суть линейные грамматики с одним нетерминальным .
символом, но пересечение языков, которые они порождают, —
это множество цепочек вида {a2nbna2n}, которое не является J
кс-языком. Этот пример вместе с тем фактом, что эти семейства
замкнуты относительно объединения, доказывает следующее
свойство.
Свойство 2. Семейства Sup(^"+), Sup(^™), Sup(#+) не
замкнуты относительно пересечения и дополнения; пересечение
двух множеств, принадлежащих одному из этих семейств, мо-
может не принадлежать Sup(^+), даже если множества порож-
порождаются грамматикой с одним нетерминальным, символом.
Вероятно, дополнение к языку из Sup(_27+) или из Sup(^7™)
может не быть кс-языком. Однако мы не располагаем приме-
примерами, чтобы доказать это2).
') В действительности этн языки линейные. — Прим. ред.
2) Справедливость этого предположения доказывается хотя бы следую-
следующим примером. Пусть язык L состоит из всевозможных цепочек вида
ЛИ2М н АфА1А2, где А\А2 — произвольные цепочки в алфавите {аи й2) и
А\ ФI. Язык L, как легко видеть хотя бы с помощью критерия из [2], не
является /сс-языком. Дополнение к i до множества всех цепочек в алфавите
•fli. яг,Ь) можно представить в виде V U V, где V — множество цепочек, не
представимых в виде АЬА, где А я А' — цепочки в алфавите {аи а2) длины.
е меньшей 2, и L" — множество цепочек, представимых в таком виде, но
Алгебраическая теория контекстно-свободных языков
219
Из рассмотренных классов языков только класс регулярных
событий (и класс конечных множеств) замкнут относительно
пересечения. Однако пересечение регулярного события и кс-язы-
ка является кс-языком f21. Имеет место также более сильный
результат, который обобщает одну хорошо известную теорему
классического анализа, принадлежащую Юнгену [20].
Теорема 2. Допустим, что г\ ? Ц. Пусть f+ — одно из
семейств ff"*, La, L+, Lm, 3 + - Пусть rjOr2 — адамаровское про-
произведение рядов Ги г2 (см. разд. 3.1). Тогда rtOr.,(iU+ для ка-
каждого r2? U+. Кроме того, если г2, г3?1<>, то ггОгзб U (Шют-
(Шютценберже [46]).
Отсюда следует, что пересечение языка нз Sup(?/+) с ре-
регулярным событием содержится в Sup (t/+) для каждого и*.
Доказательство этого факта, который связан с более простым
результатом, касающимся замкнутости относительно конечного
преобразования, будет намечено ниже, в § 8.
4.3. Категория линейных грамматик представляет, как мы
увидим, особый интерес. Сделаем несколько предварительных
замечаний, относящихся к ней. Заметим, что если L — язык,
порождаемый линейной грамматикой, то можно найти словарь
V, не пересекающийся с Vt, два гомоморфных отображения
а, а' полугруппы F(V') в F(VT), регулярное событие R над V"
и конечное множество CcF(VT) такие, что L состоит в точ-
точности из цепочек f=a(g)ca'(g), где g(LR,g — зеркальный об-
образ g, а с€ С. Таким образом, конечный процесс, применяемый
к системе цепочек (или пару согласованных конечных процес-
не входящих в L. V, очевидно, может быть порожден односторонней линей-
линейной кс-грамматикой. В то же время L", как легко проверить, порождается
грамматикой со следующей системой уравнения;
О] =alal-^-ala2-\-a1a1-\-a3a2,
a4 -f- пф,
а2 — a,a2ai -f- atasa2 -{¦ o2a2o,
a3 = aia3O| -f- <2,a3a2 + a2a3at -{¦ a2a3o2 -f-
at — a,at -\- a2a4-(- atb -(- a2b,
tb -f- a2b
(где a,—начальный символ).
Более сильный результат получен в работе: Н а i п е s L. H., Note on the
complement of a (minimal) linear language, Inform, and Control, 7, A964),
307. Там показано, что даже минимальная линейная /сс-грамматика может
порождать язык, дополнение к которому не является кс-языком. — Прим.
ред.

220
И. Хомский, М. П. Шютценберже
сов), можно, вообще говоря, связать с линейной грамматикой и
изучать соответственным способом.
Эквивалентным образом можно охарактеризовать линейный
язык несколько иначе. Пусть V'=*V*\i V- (V*={vi;Q^.iKn),
y-s={Vi: — n'^Ci^C—1}). Если [€.F(V+), определим J как ре-
результат подстановки а_,- вместо всех вхождений vt в f. Тогда
линейный язык L определяется выбором гомоморфного отобра-
отображения р полугруппы F(V') в F(Vt) регулярным событием R
над V* и конечным множеством CczF(Vt)- Теперь L—множе-
L—множество цепочек p(f) с р(/), где f€R, с?С. Ниже мы будем поль-
пользоваться этой характеристикой.
Мы можем определить специальные классы линейных язы-
. ков, налагая дальнейшие условия на регулярное событие /?, ото-
отображения а, а' и класс С. В частности, ниже мы будем рассма-
рассматривать случай, когда R — просто свободная полугруппа (ре-
(регулярное событие, определяемое автоматом с одним состоянием)
и где С содержит такие c?VT, что a(f)=?<fCty&a'([). Грамма-
Грамматику, определенную такими условиями, назовем минимальной
линейной грамматикой.
Минимальная линейная грамматика содержит один нетерми-
нетерминальный символ S и одно заключительное правило S —»с и не
содержит незаключительного правила S—>фс1|>. Таким образом,
каждая цепочка языка, порождаемая этой грамматикой, имеет
«центральную пометку» с. Это простейшее множество языков
(в рамках наших рассмотрений), более богатое, чем класс ре-
регулярных событий; мы увидим, что эти языки значительно от-
отличаются от регулярных событий многими формальными свой-
свойствами.
Для дальнейших ссылок мы приведем сейчас один частный
результат, относящийся к минимальным грамматикам. Возьмем
V, VT = W[}{c}(c=?W), а и а', как и выше. Пусть G — мини-
минимальная линейная грамматика, определенная посредством а, а'
и порождающая язык L(G). Тогда грамматика G имеет опреде-
определяющее уравнение
р = й + 2(о(щ)рв'Н: , ,.
где а, а' —отображения полугруппы F(V') в F(W).
Тогда имеем следующую теорему.
D7)
изм в), то
Алгебраическая теория контекстно-свободных языков 221
Очевидно, существует разбиение F(VT) \ L(G) = L\jU, та-
такое, что
L' = F(W)UcF(W)U((F(W)\F(A))cF(W)U D8)
[}F(VT)cF(VT)cF(VT),
но U — регулярное событие. Поэтому достаточно показать, что
язык L порождается однозначной линейной грамматикой.
_ Поскольку а—мономорфизм, то существует изоморфизм
а : F(A) —*F(V). Распространим а' на F+(A), определив а'а =
— а'(аа) для adF*(A).
Предположим, что acJ'dL. Тогда adF*(A), f'dF(W) и
{'фа'а. По определению имеются три взаимно исключающие
возможности для acf:
(И) a
(iii) а = а1аф3 и /'
?W; h,
(где аь a3?F(A); a2?A,
* (W)g; a'
D9)
D9i) в случае, если f содержит а'а как собственный пра-
правый множитель;
D9ii) в случае, если а'а содержит /' как собственный пра-
правый множитель;
D9Ш) в случае, если а'а и /' имеют цепочку ga'ai наиболь-
наибольшим общим правым множителем.
Эти три случая исключают друг друга и исчерпывают все
возможности. Мы получаем разбиение на три подмножества
Lu Z-2 и Z-з, состоящие из цепочек, удовлетворяющих условиям
(i) — (iii) соответственно. Сейчас мы должны показать, что ка-
каждый из языков порождается однозначной линейной граммати-
грамматикой.
_Для языков Lt и Z-2 этот факт очевиден. Пусть Л=2{а : а 6 Л}
и W — X{w: ш? W]. Тогда язык Z.j порождается грамматикой
E0), а язык L2 — грамматикой E1) (см. разд. 3.2).
F), E0)
1)'1с. E1)
Рассмотрим язык L3. Для каждого ad А обозначим через
В(а) множество всех цепочек wg(wdW, gdF(W)), таких, что
a'a?F+(W)g и a'a(fcF(W)wg. Ясно, что В (а) есть всегда ко-

222
Н. Хамский, М. П. Шготценберже
нечное множество, так как длина g меньше длины а'а. Язык L3
может быть порожден однозначной линейной грамматикой,
уравнения которой имеют вид
р Х(М'€ЛJ*еА }, E2)
Это проверяется непосредственно. Но мы задаем F(VT)\ L(G)
как объединение четырех попарно непересекающихся множеств
Ц, Li, Ls и L', каждое из которых порождается однозначной ли-
линейной грамматикой. Следовательно, F(Vr) \ L(G) также поро-
порождается однозначной линейной грамматикой, что и требовалось
доказать.
Заметим, что если бы в качестве а мы взяли не мономор-
мономорфизм, а «конечное преобразование без потери информации» [43],
то мы могли бы получить результат, отличающийся от теоремы
3 только тем, что строящаяся в доказательстве линейная грам-
грамматика была бы не однозначной, а имела бы ограниченную не-
неоднозначность.
4.4. Мы рассмотрели несколько подсемейств класса кс-грам-
матик, определяемых структурными свойствами составляющих
их правил. Возможны и другие принципы классификации. Так,
возможно, имеет смысл выделение класса грамматик (языков)
со звездочкой, характеризуемого следующим образом: G есть
грамматика со звездочкой, если каждому нетерминальному сим-
символу а,- грамматики G поставлено в соответствие множество 2;
нетерминальных символов и три терминальные цепочки fr f'r j"r
причем G содержит все правила вида а, -> /,', а, -> fpj^ (aj ?
?Е;), а^-*а4а;(а^, а4, а(? Е;). Это в известном смысле наиболее
«бесструктурные» кс-грамматикн. Такие языки интересны тем,
что уравнения, определяющие соответствующие степенные ряды,
можно записать, используя существенным образом только квази-
квазиобращение и сложение (как было замечено в разд. 3.2). Заметим,
в частности, что не металинейный язык Lie, определенный урав-
уравнением D2), является языком со звездочкой. В разд. 3.2 была
предложена лингвистическая интерпретация для понятия «языка
со звездочкой».
Можно было бы также классифицировать кс-языки по числу
нетерминальных символов минимальной грамматики, опреде-
определяющей степенной ряд (язык). Однако навряд лн какие-либо
интересные свойства языка связаны с этим параметром, мало
зависящим от структурных черт грамматики (за исключением
специального случая языков, определяемых грамматиками с
единственным нетерминальным символом), потому что для по-
полугрупп, в отличне от групп, грубые числовые параметры не
Алгебраическая теория контекстно-свободных языков
223
связаны сколько-нибудь интересным образом с их (полугрупп)
структурой. Заметим, впрочем, что для каждого N можно по-
построить регулярное событие, которое не может быть порождено
кс-грамматикой, имеющей меньше чем N нетерминальных сим-
символов.
Еще один принцип классификации может быть получен из
рассмотрения зависимостей между частями грамматик. Назо-
Назовем кс-грамматику неприводимой, если ни одна собственная
подсистема системы ее определяющих уравнений не образует
кс-грамматику (напомним, что терминальные цепочки должны
быть выводимы из каждого неначального нетерминального сим-
символа кс-грамматики), в противном случае грамматику будем
называть приводимой. Если кс-грамматика приводима в этом
смысле, то должны существовать собственное подмножество Si
множества ее правил и собственное подмножество Е2 множе-
множества ее нетерминальных символов, такие, что в тех местах вы-
вывода, где появляются символы из Х2, могут применяться только
правила из Ei.
Один предельный случай приводимости был изучен Гинзбур-
Гинзбургом и Райсом [18]. Следуя им, назовем кс-грамматику G после-
последовательной, если существует такое упорядочение ее нетерми-
нетерминальных символов bi, ..., а„ (где ccj есть начальный символ),
что не существует правил вида а* —* фа^, где / < i. Решение
последовательностной грамматики особенно легко определить
итеративной процедурой последовательного исключения пере-
переменных, описанной в разд. 2.3.
Для семейства <?7+ последовательностных грамматик и се-
семейства Sup(^"~) их опорных множеств Гинзбург и Райе полу-
получили следующие результаты, параллельные указанным выше.
Во-первых, ясно, что <?7+, как и ff + , — полукольцо, замкнутое
относительно квазиобращения квазнрегулярных" элементов. Со-
Соответственно Sup((^"+) замкнуто относительно объединения, ум-
умножения и итерации. Отсюда и из того факта, что SF>+<=.$>+,
следует, что Sup (j?o") с Sup (<^>>+). Более того, включение являет-
является собственным, как можно видеть из примера с граммати-
грамматикой D2), которая, поскольку она содержит один терминальный
символ, является последовательностной. Таким образом, имеет
место следующее соотношение:
Sup^o^SupG^fjrSup^). E3)
Гинзбург и Райе показали, что не существует последователь-
последовательностной грамматики для языка со словарем [а, Ъ, с, d], содер-
содержащим цепочку
а"»*-ч/ ... dbn* da"'ca"< db** d... b'^-'da^-i E4)

224
Н. Хамский, М. П. Шютценберже
(симметричную относительно с) для любой последовательности
(ft, tit, ¦ ¦ ¦, #2/1-1) положительных целых чисел, хотя этот язык
порожден грамматикой
а = adp da -\- aaa -f- аса,
p = b$b + bdadb. ^
В соотношении E3) ни _2*о, ни д* нельзя заменить ни на ка-
какое из семейств -2*т и J?+. В самом деле, грамматика E5) ли-
линейная, хотя и не последовательностная, так что §щ(Л?*)ф
фЪщ(?Р*), а грамматика D2) последовательностная, но не
металинейная, так что Sup(^+)&; Sup(^"^).
Поскольку грамматики D5) и D6) последовательностные,
мы видим, что свойство 2 (но не теорема 2) может быть рас-
распространено Sup(^+). Дальнейшие результаты относительно
последовательностных языков см. Гинзбург и Роуз [19], Ша-
мир [51].
S. ДРУГАЯ ХАРАКТЕРИСТИКА СЕМЕЙСТВА #С-ЯЗЫКОВ
В этом разделе мы разовьем несколько другой подход к оп-
определению семейств языков и покажем, как этот подход соот-
соотносится с классификацией, рассмотренной выше. Определим два
основных понятия: стандартного регулярного события и языка
Дикка.
Стандартное регулярное событие определяется конечным ал-
алфавитом X, двумя подмножествами /t и /2 произведения (X, X)
и следующим правилом: Id А тогда и только тогда, когда:
A) iexF(X)C\F(X)x', где (х, x')?J,,
(ii) f?F(X)xx'F(x), где (х, х'NЛ-
E6)
обРазом- А есть множество всех цепочек, которые на-
деожТп/ кончаются заРанее выделенными буквами и не со-
Л ямяетДН Д«уХ РЯД°М стояших бУкв. принадлежащих /2.
квазииД, (В 6 специалмой терминологии) пересечением
идеалу п ' опРеДеленного Л, с дополнением к двустороннему
Зе' п°Р0ЖДенн°му всеми произведениями хх' Их, х') 6/2)
^Гем^71Пз5Г
ЯЗЫК Дикка °2п над алфавитом из 2п букв
т^п } КЗК множеств° всех цепочек f, которые могут
ванием п= 6НЫ Д0 ПуСТ0Й "епочки последовательным вычерки-
Диккя-! Р рЯД0М СТОЯЩИХ бУкв вида x}x.,(—n<j4,n). Язык
это хорошо известный математический объект- если Ф
Алгебраическая теория контекстно-свободных языков
225
является гомоморфизмом свободной полугруппы, порождаемой
множеством {x±i}, на свободную группу, порождаемую подмно-
подмножеством {xt : г>0}, который удовлетворяет тождеству (<Р,)~ =
= фж , то ?>2п — ядро ф, т. е. множество цепочек /, таких, что
Для этих понятий имеют место следующие результаты.
Утверждение 1. Для любого регулярного события
В с F(Z) можно найти стандартное регулярное событие А и
гомоморфизм a: F(X) —*F(Z), такой, что В = аА.
Стоит заметить, что не только В = аА, но что, кроме того,
каждая цепочка fdA имеет ту же степень неоднозначности, что
и соответствующая цепочка af?B. Иначе говоря, если В —
= Sup (p), то можно найти у такое, что j4 = Sup (у), и для ка-
каждой цепочки f {у, /) = (р, af).
Утверждение 1 можно обобщить на кс-языки, используя
следующие свойства языка Din.
Свойство 1. D2n порождается однозначной кс-граммати-
кой.
Чтобы получить такую грамматику, введем 2п+\ нетерми-
нетерминальных символов a±i A ¦<!¦<«), р. Рассмотрим теперь 2га+ 1
уравнений:
(i) a, = x,(l-
E7)
(ii) P = (l-2«»«)~.
(Обозначение см. разд. 3.2.)
Интуитивно р можно интерпретировать как совокупность
всех цепочек, которые могут быть сокращены до пустой после-
последовательности вычеркиванием пар рядом стоящих букв хгх-{.
Каждое а; есть совокупность всех слов из Sup ((S), которые
начинаются с Xi и не имеют собственных начальных или конеч-
конечных отрезков, принадлежащих Sup ((S). Из уравнения E7i) сле-
следует, что каждая цепочка f 6 Sup (aj) имеет одно и только одно
разложение
f ff..fmx^, E8)
где каждая цепочка }j принадлежит множеству Sup (а,) (где
\ф—it потому что мы хотим, чтобы начальная буква л:,- сокра-
сокращалась только с конечной буквой x-i).
Аналогично каждая цепочка /ё Sup (P) имеет одно и только
одно разложение f=*fi...fm, где цепочки jj принадлежат
М sup (a,).

226
Н. Хамский, М. П. Шютценберже
место следующий результат, аналогичный утвержде-
утверждение * ¦
Утверждение 2. Любой кс-язык La F(Z) определяется
целым числом п, стандартным регулярным событием А над сло-
словарем XZn = {x±u l-<?i<-n}, гомоморфизмом q>: F(X2n) -*F(Z)
и правилом Л = Ф(Л П D2n). [48], [49], [II], [12].
Снова, как и выше, из этого утверждения следует, что це-
цепочки порождаются с соответствующей степенью неоднознач-
неоднозначности. Кроме того, можно выбрать Л так, что (х, *') б Л, если
х принадлежит некоторому подмножеству X (см. [48]).
Специальные подсемейства языков рассмотренного выше
типа можно определять, накладывая условия на стандартное
регулярное событие А и гомоморфизм <р. Предположим, что мы
взяли стандартное регулярное событие Л над алфавитом X U У
где Х = {х±(: \*Ci4in}, Y={y±i: 1-^-i^.m}, определенное сле-
следующими условиями на Л и /2:
/,={(*. Xj) : ;>0},
/i={(*<, х}): знак (t) =?знаку (j)} U Ши ys) : »<0 или />0} U
U {(*(, Уд : КО или /<0} U {(уи X}) : />0 или />0}. E9)
Здесь каждая цепочка имеет вид fgg'f, где f, f'dF(X);
g, g"?F(Y); f, g (соответственно f, g') содержат буквы только
с положительными (соответственно отрицательными) индек-
индексами. Если мы обозначим через Х+ и Х~ подмножества X, со-
состоящие соответственно из букв с положительными и отрица-
отрицательными индексами (аналогично для Y* и У"), то можно опи-
описать допустимые и недопустимые переходы с помощью матрицы
F0), где 1@) означает, что переход от элемента, обозначаю-
обозначающего строчку, к элементу, обозначающему столбец, возможен
(или нет); U есть матрица, состоящая только из единиц, а 0
есть матрица, состоящая только из нулей:
__ У+ У Х+ X'
F0)
есть язык
У+
У~
х+
X'
0
0
и
0
и
0
0
0
0
0
и
0
0
и
0
II
л4авитом 7Tv^v A п;°Гл \
*\T U Y)- Если fe^A гДе f
)] Уд°влетвоРяет тому условию, что
^Г1гг:г°йг
г„
Алгебраическая теория контекстно-свободных языков
227
ниях второго абзаца разд. 4.3 должно быть, что g=f. Ясно, что
если а есть гомоморфизм F(X U У) в F(VT), то а(А П DXr)
есть линейный язык. Кроме того, если добавить условие, что
yt — e для !<0 и yt = c для каждого !>0, где axt (fc F(Vt)cF(Vt)
для каждого i, то Л = а(Л П й^г) будет минимальным линей-
линейным языком с символом с в качестве центральной метки, при-
причем каждый минимальный линейный язык определяется таким
выбором а. Это дает независимую характеристику минималь-
минимальных линейных языков.
Кроме того, добавляя к Л некоторую пару, можно ограни-
ограничить определенный выше канонический язык А таким образом,
что {f:f?F(X+) и для некоторого g, fg?A и g? F (Y)F(X)}
явится произвольным регулярным событием (а не свободной
полугруппой над Х+, как выше), так что L = a(A П DXy) будет
произвольным линейным языком. Таким образом, мы получим
независимое определение понятия «линейный язык». Заметим,
что это дальнейшее ограничение на h влияет только на те эле-
элементы матрицы F0), которые находятся на главной диагонали.
Таким же способом можно дать определение «металиней-
ного языка». Рассмотрим, например, металинейный язык, поро-
порожденный грамматикой с уравнениями
F1)
В этом случае матрица для соответствующего стандартного
регулярного события имеет вид
Л 1 Л\ У\ 2
л 3
хг
хг
X}
и
0
0
и
и
0
0
и
и
0
0
и
F2)
Х2 0
о
о и
Каждый металинейный язык и только металинейные языки
могут быть определены с помощью стандартного регулярного
события с матрицей существенно такого вида (может быть,
с дополнительными ограничениями на главную диагональ).
Таким образом, утверждения I и 2 дают возможность весьма
естественным образом определить полный класс кс-языков и
различные подсемейства этого класса независимо от подхода,
которого мы придерживались в предыдущих разделах,

228
Н. Хомский, М. П. Шютценберже
в. АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ
6 1. В работе Поста [36] показано, что так называемая про-
проблема соответствий рекурсивно неразрешима. Если 2 =
f/Y gt) (fn, gn)} есть последовательность пар цепочек,)
кажем, что последовательность /= (i'i, ..., im) целых чисел
^) д 2
скажем,
4i
n) удовлетворяет 2, если
(
>|, ->«.-*«,-*«.¦ F3)
Проблема соответствий состоит в распознавании того, суще-
существует ли при данном 2 последовательность индексов, удовле-
удовлетворяющая Б. Заметим, что Б либо не удовлетворяется никакой
последовательностью индексов, либо удовлетворяется бесконеч-
бесконечным числом последовательностей, так как если (lt lm)
удовлетворяет Б, то (iit ..., im, iu ..., im) тоже удовлетво-
удовлетворяет 2. Пост показал, что не существует алгоритма, позволяю-
позволяющего распознать при произвольном 2, какой из этих двух слу-
случаев имеет место.
Проблему соответствий можно непосредственно переформу-
переформулировать в терминах минимальных линейных грамматик. Если
дано 2 = {(fi, gi), ..., (fn, gn)}, построим грамматику 0B)
с одним нетерминальным символом s и определяющим уравне-
уравнением
S = a + flSgl+...+fnSg*, F4)
где а есть символ, не встречающийся ни в цепочках fi, ни в це-
цепочках gt. Ясно, что последовательность индексов, удовлетво-
удовлетворяющая Б, существует тогда и только тогда, когда 0B) поро-
порождает цепочку faf. Иначе пусть Lm есть язык «зеркального
отражения», состоящий из всех цепочек faf, где f?F(Vr), и
пусть L(GB)) есть язык, порождаемый грамматикой О. Тогда
либо не существует последовательности индексов, удовлетво-
удовлетворяющей 2, и в этом случае Lm Л ?@(Б)) пусто, либо суще-
существует бесконечно много последовательностей индексов, удовле-
удовлетворяющих 2, и в этом случае Lm П ?@B)) бесконечно. Из
неразрешимости проблемы соответствий и из того факта, что
^¦т порождается линейной грамматикой с одним нетерминаль-
нетерминальным символом, непосредственно следует теорема.
Теорема неразрешимости 1. Не существует алго-
алгоритма, позволяющего распознать для двух произвольных кс-
грамматик О, и 02, порождающих соответственно языки Z., и 1Ъ
вляется ли 2., (") L, пустым или бесконечным. Это верно также
*я случая, когда О, и 02 — минимальные линейные грамма-
ки, и для случая, когда G» — фиксированная грамматика
языка Lm.
Алгебраическая теория контекстно-свободных языков
229
Легко видеть, что для односторонних линейных грамматик
проблема распознавания пустоты и конечности пересечения раз-
разрешима. Но мы видим, что для простейших грамматике рамках
нашего рассмотрения, которые более богаты, чем класс регу-
регулярных событий, эти проблемы уже не разрешимы.
Это замечание обобщено в работе Бар-Хиллела, Перлеса н
Шамира [2], где показано, что многие проблемы, относящиеся
к тсс-грамматикам, рекурсивно неразрешимы. Коротко их метод
заключается в следующем. Возьмем в качестве VV множество
{а, 0, 1}. Если 2={(fi, gi) (fn, gn)} есть множество пар
цепочек над словарем {0, 1} (т. е. ft, gid F{Q, 1}), обозначим
через ?(Б) множество всех цепочек
10'* ... 10'% ¦¦¦ f,agj ...gf aO''l ... 0y'l, F5)
где 1 < i, ik, у, /,< п.
Яснее можно сказать так: будем использовать T=W в ка-
качестве кода числа i. Тогда каждая цепочка из ?B) строится
следующим образом: выбираются последовательности индексов
/= (<!, ... ,ik) и /= (Д. ..., ji) и образуется
ik...ixafti...f.
¦g,*h •¦¦Jr
F6)
Язык ?(Б) играет такую же роль, как язык, порожденный
уравнением F4) в доказательстве теоремы неразрешимости.
Ясно, что это кс-язык [он порождается в действительности мета-
линейной грамматикой, получаемой, очевидно, видоизменением
уравнения F4)]. Но из теоремы 3 в разд. 4.3 непосредственно
следует, что дополнение F(Vt) \ LB) языка ?B) по отноше-
отношению к словарю W является кс-языком и что, исходя из его
грамматики, можно построить грамматику языка ЛB). (Заме-
(Заметим, что для определения ?B) мы могли бы вместо выбран-
выбранного нами кода l=10* использовать любой другой код.)
Вместо языка зеркального отражения Lm, использованного
в доказательстве первой теоремы неразрешимости, рассмотрим
теперь язык «двойного зеркального отражения» Ldm, состоящий
из всех цепочек вида
xsax2ax2axi, где xi н хг суть цепочки над алфавитом {0, 1}. F7)
Нетрудно показать, что язык Ldm и его дополнение по от-
отношению к словарю Vt являются кс-языками.
Заметим, что
^ (Б) П LdK = {7„... 7,0^ ... f,agtt ... leu, ... 7k). F8)
где (ii, ..., in) удовлетворяет Б (т. е. где ft ¦ ¦ ¦ f, =gt ¦ ¦ ¦
• ¦ ¦ gi )• Заметим также, что бесконечное множество цепо-
16 Зак.

230
Н. Хамский, М. П. Шютцепберже
чек вида F8) не может образовывать /сс-язык (и тем более
регулярное событие).
Допустим теперь, что существует положительное решение
проблемы соответствий для 2, т. е. существует последователь-
последовательность индексов, удовлетворяющая 2. Тогда, как мы заметили
выше, существует бесконечно много таких последовательностей.
Следовательно, ?B) П Ldn — бесконечно, поэтому оио не
является ни регулярным событием, ни кс-языком.
Допустим далее, что не существует последовательности ин-
индексов, удовлетворяющей 2. Тогда 1B) П Ldm пусто, поэтому
оно является и регулярным событием и кс-языком. Но /.B)
и Ldm являются кс-языками, н при фиксированном 2 можно
построить для них кс-грамматики GB) и Gdm (которые яв-
являются в действительности металинейными). Таким образом,
если бы существовал алгоритм, позволяющий распознавать,
является ли пересечение языков, порождаемых двумя /сс-грам-
матиками 0B) н Gdm, пустым языком, конечным языком, регу-
регулярным событием или кс-языком, то этот алгоритм давал бы
также решение общей проблемы соответствий.
Нами доказана, таким образом, вторая теорема неразре-
неразрешимости.
Теорема неразрешимости 2. Не существует алго-
алгоритма, позволяющего распознавать для кс-грамматик Ог и Gb
является ли пересечение языков, порождаемых ими, пустым
языком, конечным языком, регулярным событием или кс-язы-
кс-языком. Это остается верным для случая, когда обе грамматики
металинейные, и для случая, когда G2 есть фиксированная
грамматика языка.
Пусть Gdm есть кс-грамматика, порождающая дополнение
Ldm языка Ldm (все дополнения рассматриваются теперь по от-
отношению к словарю VT). Если дано 2, пусть 5B) будет кс-
грамматикой, порождающей дополнение 1B) языка АB) (су-
(существование такой грамматики гарантируется теоремой 3
Разд. 4.3). Рассмотрим грамматику G, порождающую язык
' )=^*п U L(X). Ясно, что G есть кс-грамматика и что она
^к быть построена, исходя из Gdm и GB), но дополнение
?а L^ совпадает с множеством Ld U IB)=Idm n
Mi). Как мы знаем из второй теоремы неразрешимости, не
^уществует алгоритма, позволяющего распознавать при данном
ком еТСя Ли это множество пустым языком, конечным язы-
. регулярным событием или кс-языком. Но при данном 2
w есть ««-грамматика.
Алгебраическая теория контекстно-свободных языков
231
Поэтому мы можем сформулировать третью теорему нераз-
неразрешимости.
Теорема неразрешимости 3. Не существует алго-
алгоритма, позволяющего распознавать для кс-грамматики G, яв-
является ли дополнение языка, порожденного G, пустым языком,
конечным языком, регулярным событием или кс-языком.
В частности, не существует общей процедуры, позволяющей
распознавать, порождает ли кс-грамматика G универсальный
язык F(Vt), порождает ли грамматика G регулярное событие
(поскольку дополнение к регулярному событию является регу-
регулярным событием). Следовательно, не существует алгоритма,
позволяющего для кс-языков Lt и L2 распознавать, существует
ли преобразователь, отображающий Lt на L2, поскольку все ре-
регулярные языки и только они могут быть получены конечным
преобразованием из кс-языка F(Vt) (Гинзбург и Роуз, личное
сообщение). Кроме того, не существует общего метода, позво-
позволяющего распознавать, являются ли две кс-грамматики экви-
эквивалентными, т. е. порождают ли йни один и тот же язык; в са-
самом деле, если бы существовал такой метод, то с его помощью
можно было бы распознать, эквивалентна ли кс-грамматика G
грамматике 0^, порождающей F(Vt)- Отсюда непосредственно
следует, что не существует алгоритма, позволяющего распозна-
распознавать для двух кс-грамматик, содержится ли язык, порождае-
порождаемый одной из них, в языке, порождаемом другой грамматикой;
в самом деле, это давало бы решение проблемы эквивалент-
эквивалентности.
Эти результаты были получены для языков над трехэлемент-
трехэлементным словарем W, но ясно, что при соответствующем перекоди-
перекодировании они могут быть применимы и к языкам над словарем
из двух или более букв. Этот вопрос детально исследован в ра-
работе Бар-Хиллела, Перлеса и Шамира [2].
6.2. В разд. 4 мы заметили, что конечные процессы, приме-
применяемые к парам цепочек, допускают естественную формули-
формулировку в терминах линейных грамматик. В частности, как мы
только что видели, проблема соответствий может быть описана
непосредственно как проблема, относящаяся к минимальным
линейным грамматикам. Это верно и для другой комбинатор-
комбинаторной проблемы, также поставленной Постом, а именно так на-
называемой «таг-проблемы».
Обобщенную таг-проблему можно сформулировать следую-
следующим образом, Пусть W—множество цепочек (свободная полу-
полугруппа) над некоторым конечным словарем, и пусть Р есть
конечное подмножество непустых цепочек из W, удовлетворяю-
удовлетворяющих тому условию, что для каждой цепочки из W не более чем
16*

232
Н. Хамский, М. П. Шютценберже
один ее начальный отрезок принадлежит Р. Иначе не суще-
существует Pi, P2, ti>i, tt>2, ®з (Pi? P, W{dW) таких, что р^фрг и
W\ =piWz—РгЩ. Пусть V есть множество цепочек из W, ника-
никакие начальные отрезки которых не принадлежат Р. Иначе го-
говоря, vdV тогда и только тогда, когда не существует pdP,
такого, что v = pw, где w б W. Ясно, что V есть рекурсивное и
даже регулярное множество. Пусть а—отображение Р в W
[таким образом, а определяет множество пар цепочек (р, ш),
где w — ap, p? P, w(iW]. Определим отображение Т на W, где
Tf = f'ap, если f = pf,
77 = Я, если f?V(H?W). F9)
Рассмотрим следующую задачу. Существует ли для данной
цепочки f целое число я такое, что
Т"! = Н? G0)
Если рассматривать Т как определение вычисления на не-
некоторой машине Тьюринга, то наша задача есть проблема
остановки для этой машины Тьюринга. Минским [30] было по-
показано, что проблема G0) рекурсивно неразрешима.
Таг-проблема в формулировке Поста — это специальный
случай проблемы G0), где Т удовлетворяет следующим допол-
дополнительным условиям: Р — это множество всех цепочек длины ft
для некоторого фиксированного ft >- 2, ар зависит только от
самого левого символа р. Проблема G0), как показал Минский,
неразрешима даже при этом ограничении. Этот результат
является несколько неожиданным ввиду детерминированности
(моногенности), порождающей процедуры Т.
Чтобы удобнее было переформулировать обобщенную таг-
проблему в терминах минимальных линейных грамматик, за-
заметим, что она может быть представлена следующим образом.
При данных W, Р, V, а, Т, как выше, проблема G0) имеет
положительное решение тогда и только тогда, когда
существуют цепочки рх, .... рп?Р и v?V, такие,
что
арп.
G1)
Теперь обобщенную таг-проблему можно сформулировать
как следующую проблему, относящуюся к линейным грамма-
грамматикам. При данных W, Р, V, а, Т определим грамматику G
порождающую язык L(G), с помощью уравнения
G2)
Алгебраическая теория контекстно-свободных языков
233
где О;б V, ptdP и с ? 1У-—центральная пометка. Определим
язык M(f)={fgcg:g? W] [таким образом, M(f)=fLm, где Lm
есть язык «зеркального отражения», определенный выше]. То-
Тогда решение проблемы G1) [или, что то же самое, проблемы
G0)] положительно тогда и только тогда, когда пересечение
L(G) с M(f) непусто. Мы видим, таким образом, что не суще-
существует алгоритма, позволяющего распознавать при фиксирован-
фиксированной цепочке f, имеет ли язык M(f) непустое пересечение с язы-
языком, порождаемым грамматикой, удовлетворяющей уравнению
G2) (даже для специального случая, когда Р есть множество
всех цепочек длины для фиксированного k ^2 и ар зависит
только от самой левой буквы р).
Заметим, что первая теорема неразрешимости также непо-
непосредственно следует из неразрешимости таг-проблемы. В са-
самом деле, и таг-проблема и проблема соответствий относятся
к мощности пересечения минимального линейного языка L
с языками M(f), где в случае проблемы соответствий f = e и L
выбирается произвольно, а в случае таг-проблемы f произ-
произвольна и L удовлетворяет уравнению G2).
7. НЕОДНОЗНАЧНОСТЬ
7.1. Мы назвали степенной ряд г характеристическим, если
каждый коэффициент {г, f) есть либо нуль, либо единица. Мы
говорим, что кс-грамматика однозначна, если главный член ее
решения есть характеристический степенной ряд. В этом случае
каждое предложение, которое она порождает, имеет только
одно структурное описание и «стирание скобок» не приводит
к неоднозначности. Назовем кс-язык существенно неоднознач-
неоднозначным, если каждая его грамматика неоднозначна. Хорошо из-
известно, что ни одно регулярное событие не является существен-
существенно неоднозначным, т. е. каждое регулярное событие есть опор-
опорное множество характеристического степенного ряда, являюще-
являющегося главным членом решения односторонней линейной грам-
грамматики [14], [37]. Однако это не переносится на полный класс
кс-грамматик. Париком [34] было доказано, что существуют
существенно неоднозначные тсс-языки.
Примером существенно неоднозначного языка является мно-
множество
{a"bmcp :n — m или m = p). G3)
Здесь цепочки вида anbncn должны иметь степень неодно-
неоднозначности, равную по меньшей мере двум, для любой кс-граи-
матики, порождающей G3) [и существует кс-грамматика, по-

234
Н. Хамский, М. Я. Шютценберже
рождающая G3) со степенью неоднозначности, равной точно
двум].
У нас нет примеров, иллюстрирующих объем понятия суще-
существенной неоднозначности для кс-языков или для специальных
типов тсс-языков.
Заметим, что из первой теоремы неразрешимости (разд. 6)
непосредственно следует, что не существует алгоритма, позво-
позволяющего распознавать, является ли кс-грамматика или даже
линейная грамматика неоднозначной. В самом деле, пусть, как
и выше, 2= {(},, ?¦[), . . ., (fn, gn)} есть последовательность пар
цепочек. Выберем я-И новых символов ха, ..., хп и построим
грамматику Gs с правилами: Sj-+x0, Sf-+XiSfft A<1<я) и
грамматику Gg с правилами: Sg—>x,,, Sg—>xtSggi (\ <Ci*Cn).
Ясно, что грамматики G/ и Gg однозначны и проблема соответ-
соответствий для Б имеет положительное решение тогда и только то-
тогда, когда существует цепочка, порождаемая обеими грамма-
грамматиками Gf и Gg, т. е. тогда и только тогда, когда является не-
неоднозначной грамматика Ofg, определенная следующим обра-
образом: Gfg содержит правила Gf, Ge и правила S-+Sf, S-+Sg, где
S есть начальный символ грамматики Gfg. Следовательно, не-
невозможна процедура, позволяющая распознавать для произ-
произвольного Б, является ли грамматика Gfg, соответствующая Б,
неоднозначной.
Грамматика Qjs линейна с тремя нетерминальными симво-
символами и центральной пометкой, и мы видим, что для такого
класса грамматик проблема неоднозначности неразрешима. Ве-
Вероятно, это замечание можно обобщить на грамматики с двумя
нетерминальными символами. Однако остается открытым сле-
следующий вопрос: остается ли проблема неоднозначности нераз-
неразрешимой для минимальных линейных грамматик1).
Резюмируя все, что сказано здесь о неоднозначности, сфор-
сформулируем следующие результаты в виде теорем.
Теорема неоднозначности 1. Существуют суще-
существенно неоднозначные кс-языки.
Теорема неоднозначности 2. Не существует алго-
алгоритма, позволяющего распознавать, является ли кс-грамматика
(которая может быть даже линейной с центральной пометкой)
неоднозначной.
) Неразрешимость проблемы распознавания неоднозначности для ми-
минимальных линейных грамматик доказана в работе Грейбах [G г е i b а с h S. А.,
undecida bility of the ambiguity problem lor minimal linear grammars, In-
lortn. and Control, 6 A963), 119—125]. — Прим. ред.
Алгебраическая теория контекстно-свободных языков
235
8. КОНЕЧНОЕ ПРЕОБРАЗОВАНИЕ
Опишем теперь одно особенно простое семейство преобра-
преобразований языка в язык. Первое и наиболее важное преобразо-
преобразование — гомоморфизм.
Пусть L есть язык над терминальным словарем Z, и пусть
каждому z(iZ сопоставлен язык Lz над другим словарем X.
Обозначим через 61 множество всех цепочек (над X), которые
могут быть получены следующим образом: берется слово
g:zlzt ... zt ?L, каждое zt заменяется произвольным ело-
I 2 m *
вом из Lzt . Название «гомоморфизм» не нуждается в объяс-
объяснении. В самом деле, если рассмотреть кольца A(Z) и А(Х)
формальных степенных рядов от переменных z(:Z и xdX и
обозначить через 6 гомоморфизм A(Z) в А(Х), индуцированный
отображением 6г, равный формальному степенному ряду, соот-
соответствующему языку Ц, то б! есть опорное множество образа 6
формального степенного ряда, соответствующего языку L.
Это можно интерпретировать в рамках наших предыдущих
рассуждений, если L и все Lz суть кс-языки. Предположим
в этом случае, что язык L порождается /сс-грамматикой (с не-
нетерминальным словарем У) и что каждый язык Lz порождается
кс-грамматикой Gz (со множеством нетерминальных символов
Yz и начальным символом !/г, о). Допустим, что множества Уг
попарно не пересекаются; рассмотрим кс-грамматику & с не-
нетерминальным словарем Y\JZ[) U Yz (z?Z). (Попросту, мы
отождествляем каждое z с у2,о.) Ясно, что грамматика G поро-
порождает в точности язык QL.
Обобщим теперь эту конструкцию на следующий тип кон-
контекстной зависимости: пусть Ri (id!) и Rr(i'?I') — два конеч-
конечных множества регулярных событий, такие, что каждая цепочка
gdF(Z) принадлежит одному и только одному элементу ка-
каждого множества. Пусть, кроме того, каждой тройке (г dZ,
(€/, i'dl') сопоставлен язык L(Z,i,n наД словарем X.
Заменим в каждой цепочке y = z.z. ...г, каждое г,
произвольной цепочкой из языка L(Zj , I, i'\, где / и Г удо-
удовлетворяют тому условию, что цепочка
при-
принадлежит Л,, а цепочка Zj ...zf принадлежит/?;. Легко
доказать, что без потери общности можно допустить, что для
любой цепочки g, принадлежащей некоторому множеству Ri,, и
для zd.Z множество Ri,, которое содержит gz, зависит только
-" индекса lt и буквы г. Другими словами, мы можем допу-

236
И. Хамский, М. П. Шютценберже
стить, что задано множество состояний /, функция перехода
i\iZ-+l и начальное состояние iodl, такие, что г., г, ...
z fR, тогда и только тогда, когда i есть состояние, кото-
"' h-\
рое можно достичь из to, идя по цепочке zjzj ... гу .
Подобная конструкция применяется и к Rt; ради ясности
будем записывать соответствующее отображение как левое
умножение. Имея два отображения IXZ-+I и ZX.I'-*!', обо-
значим через og для каждого g = zJzj ...zj ?F(X) после-
последовательность троек
(',. V '-)('»• 2v '«-О • ¦ • ('*¦ zv '«-*+0 • ¦ ¦ ('«¦zv '•)¦ <74>
где /; определяется индуктивно:
В этих обозначениях описанное преобразование можно рас-
рассмотреть как состоящее из двух шагов:
(i) замена каждой цепочки g?L на цепочку
°? = ('V zj. i'm) ¦ ¦ ¦ {lmzj • '!)> наД алфавитом U, состоя- G6)
щим из троек ((, z, i');
(ii) замена в ag каждой тройки (it, zy , »^_А + 1) произволь-
произвольй ?( / ^
ной цепочкой языка
, /s, f^
( )
Поскольку шаг (ii) есть просто гомоморфизм, достаточно
рассмотреть шаг (i). Для этого обозначим через U множество
всех троек (г, 2, /') и рассмотрим язык U, полученный из
языка L добавлением к его грамматике всех правил вида
г1-*A, Zj, (') (с произвольными l?I и i'dГ).
Ясно, что цепочка V принадлежит множеству {og.gdL}
тогда и только тогда, когда она удовлетворяет условию G5)
или, другими словами, когда она принадлежит регулярному
событию Л, определенному условием G5) на множество всех
Цепочек F(U) над алфавитом U.
Следовательно, шаг (i) состоит из последовательного при-
применения двух преобразований — гомоморфизма языка L во
множество всех цепочек над U (дающего V) и пересечения U
с Регулярным событием.
Дадим теперь окончательную интерпретацию: для каждой
ОчКи * <? Z обозначим через \хг матрицу, строки и столбцы
Алгебраическая теория контекстно-свободных языков
237
которой занумерованы парами (I <? /, /' (? /') и элементами ко-
которой служат
цгA, i')(i", «'")= тройке (С, г, «'"), если
i">=lz и t' = zi"' = 0 в других случаях. G7)
Затем, если мы вычислим де,. цг, . ¦¦•• V-z, =Hg". легко
проверить, что элемент (i, i'^)(im, i\) матрицы \ig это в точ-
точности eg. Отсюда легко следует, что {ag:g ? L) — L' f| R есть
тоже кс-язык. Действительно, |.i является гомоморфизмом, так
как мы заменяем каждый нетерминальный символ матрицей
\iy, элементы которой есть новые нетерминальные символы, и
проверяем, что ц коммутирует с подстановками, использовав-
использовавшимися для определения языка как решения системы уравне-
уравнений. С другой стороны, так как ц есть образ наших уравне-
уравнений, он дает новую систему уравнений обычного типа, которые
в точности определяют язык L' Л R [46]. Еще проще мы можем
определить ц', как выше, только вместо тройки (iu zs, i') возь-
возьмем формальный степенной ряд, соответствующий языку
L(zh i, /'). Тогда два шага нашей конструкции объединяются
в один, а степенной ряд, соответствующий языку (над X), по-
полученному нашим преобразованием, — это просто элемент мат-
матрицы
2(Ъ €/) G8)
На основе сказанного строится доказательство теоремы 2 из
разд. 4.
9. СВЯЗЬ С ТЕОРИЕЙ АВТОМАТОВ
До сих пор мы изучали порождающие процессы, порождае-
порождаемые ими системы структурных описаний, а также финитные
отображения этих языков с абстрактной точки зрения. Для
того чтобы связать эти замечания с теорией автоматов, удобно
внести в рассмотрение временную асимметрию.
Автомат М можно рассматривать как устройство, состоящее
из множества состояний 2 {память М), которое допускает или
(что то же самое) порождает последовательность символов над
словарем (алфавитом) V в соответствии с конечно формули-
формулируемыми предписаниями (которые можно задать, сопоставляя
с каждым и 6 V отображение ф„ множества 2 в себя или во
множество подмножеств Б в случае «недетерминированного»
автомата). Если мы отметим начальное состояние и множество
конечных состояний, то тем самым мы определим язык M(L),
состоящий из цепочек, которые допускаются автоматом, когда

// Хамский. М. П. Шютценбержр
переходит в соответствии с предписаниями or начально'о
°Н ояния в заключительное, причем переход из состояния
^f's в состояние S'<E ? с допущением 1> происходит гогля и
ько тогда, когда грг5=5' [или в случае неяетерминнровэн-
*°го автомата, когда S'?rp, (S)]. Объем памяти автомата Л4 или
быстрота ее роста в процессе вычисления дает некоторую ха-
тернстику языка ЦМ), в терминах которой можно сравни-
сравнивать рассмотренные нами семейства языков.
Для данного множества цепочек языка L будем писать,
что \~Y в случае, если для всех g fg d L тогда и только тогда,
когда f'g?L. Ясно, что знак <~- выражает эквивалентность.
Более того, очевидно, что классы эквивалентности, определен-
определенные отношением —¦, можно взять в качестве состояний авто-
автомата M(L), допускающего L, поскольку вся информация о це-
цепочке /, существенная для дальнейшего вычисления в автомате
M(L), когда он читает /, определяется классами эквивалент-
эквивалентности, к которому принадлежит /. Заметим, что язык L есть
объединение некоторых из этих классов эквивалентности и что
отношение f~f влечет отношение fg~f'g для всех g.
Кроме того, при данном g будем писать, что /==/' тогда и
только тогда, когда для всех g gf~gf. Ясно, что f = /' тогда
и только тогда, когда для всех g, g' gfg' — gf'g'. Таким обра-
образом, отношение =- симметрично, и легко показать, что если
Д = /2 н fs== fi, то /\=/з, т- е- отношение = есть конгруэнция,
=-классы во множестве F(V) можно перемножать, причем по-
получается полугруппа частных полугруппы F(V). Эта полу-
полугруппа частных F'(V)=<pF(V) такова, что 1 = ф-1ф1 и канони-
канонически ассоциирована с Lo [41].
Это замечание связывает нашу теорию с теорией полугрупп.
Эта связь интересна тем, что в некоторых случаях классы
(полугруппа частных) имеют простую интерпретацию на языке
автоматов и обратно — что некоторые алгебраические понятия
(в частности, расширение) получают простую интерпретацию.
Вернемся теперь к проблеме характеризации семейств язы-
языков в терминах автоматов. Хорошо известно, что подмножество
кс-языков однозначно характеризуется тем, что для
каждого языка /.? SupCj'J") существует автомат M(L) с конеч-
конечной памятью, допускающий L.
Рассмотрим теперь семейство Supf^o), т. е. множество
орных множеств степенных рядов, которые являются реше-
нями систем «односторонних линейных» уравнений с положи-
льными или отрицательными целыми коэффициентами. Как
заметили, Z.?Sup(.2*o) тогда и только тогда, когда
А.1г?С>р..и
контс:.сгно свободны»: языкоо
239
/,--Snp(»-i — г?), где гь г>E(j?'o )¦ «Можно показать, что следую-
м\че утверждения эквивалентны:
(\) L 6 Sup {JT«)\
(ii) существует одно-однозначное соответствие между ~-
K.iacca'.tn для L и конечномерным пространством целочисленных
векторов u(f), таких, что для каждого х€ V, v(fx) —v(f)\ix, где
\ix есть их матрица;
(iii) /^^изоморфна некоторой полугруппе конечномерных
целочисленных матриц [т. е. матриц ц из (ii)];
(iv) L допускается автоматом M(L), множеством состояний
которого служит конечномерное пространство целочисленных
векторов, а функция перехода определена, как в (id).
[(Шютценберже [44] — пусть класс автоматов Л совпадает
с классом автоматов, определенных в G9 iv).]
Рассмотрим следующие два ограничения на класс автома-
автоматов JL.
(i) существует N такое, что для каждого
f€F(V)\\v(f)\\<N;
(ii) для всех /, /', f"€F{V) и е > О
lim е-" || г>(/ТП 11=0.
(80)
где ||иII есть длина вектора в обычном смысле.
Ясно, что (80 i) влечет (80 ii). Кроме того, ясно, что L есть
регулярное событие [т. е. L ? Sup (j?o)] тогда и только тогда,
когда (80 i) удовлетворяется для некоторого автомата класса
Л, допускающего L. Автомат класса Л, удовлетворяющий ус-
условию (80 ii) в работе Шютценберже [47], где изучаются такие
устройства, назван автоматом с конечным, числом, счетчиков.
Можно показать, что (80 ii) означает, грубо говоря, что объем
информации (в битах), накапливаемой в памяти, растет не
быстрее, чем линейная функция от логарифма длины входного
слова.
Интересно заметить, что (как раз в случае полного класса
/сс-грамматик) не существует алгоритма, позволяющего опреде-
определить для данного автомата M?uf, допускается ли f автоматом
М [28]. Кроме того, легко показать, что если неразрешима деся-
десятая проблема Гильберта (проблема существования целочислен-
целочисленного решения произвольного диофантова уравнения), то эта же
проблема также неразрешима для автомата с конечным числом
счетчиков [47].
Рассмотрим теперь автомат М следующего вида: его состоя-
состояния (~ -класса входного языка автомата М) отождествляются
с цепочками над некоторым новым («внутренним») алфавитом,

„, Н. Хомский, М. П. Шютценбержв
для каждого v? V функция перехода («вычислительное пред-
представление») Ф»:[~-класс f] — [~-класс fv)] состоит в дописыва-
дописывании или вычеркивании букв в правом конце цепочки над вну-
пенним алфавитом, сопоставленной с [~-класс f]. Такой ав-
автомат в соответствии с обычной терминологией назовем авто-
иатом с магазинной памятью или PDS-автоматом. Такие ав-
^аТьГсоставляют некоторый частный подкласс класса линейно
ограниченных автоматов, изучавшихся Майхиллом [31], Ритчи
[39].
Если М есть PDS-автомат, то язык L, который он допу-
допускает, — кс-язик и каждый кс-язык может быть получен с по-
мошыю гомоморфного отображения из языка, допускаемого
PDS-автоматом [48], [49]. В частности, если D есть язык Дикка
н А есть стандартное регулярное событие (см. разд. 5), то
допускается PDS-автоматом.
Недетерминированный PDS-автомат отличается от автомата
описанного выше типа только тем, что ф„ отображает состояние
во множество состояний. Теперь можно непосредственно дока-
доказать, что кс-языки [языки класса Sup(t7 + )] в точности те, кото-
которые допускаются недетерминированными PDS-автоматами [11],
[12].
ЛИТЕРАТУРА
1. A J d u k i e w i с z К., Die syntaktische Konnexitat, Studla Phllosophlca,
1 A935), 1—27.
2. Bar-Hill el Y., Peries M., Shamir E., On formal properties of
simple phrase structure grammars, Tech. Report 4, July 1960.
3. Bar-Hi II el Y., Peries M., Shamir E., Applied Logic Branch, Zeit.
fur Phonetik Sprachwissenschaft and Kommunikatlonsforschung 14,
№2 A961), 143-172.
4. Bar-Hi 1 lei Y., Peries M., Shamir E., Finite state languages, Bull.
Research Council Israel, 8F A960), 155—166.
5. Blrkeland R., Sur la convergence de developpement, qui expriment le
racins de l'equation algebrique generale, C. R. Acad. Sciences, 171
A920), 1370-1372, 172 A921), 309-311.
6. CulikR-, Some notes on finite state languages, Casopis pro pestovant
Mat., 86 A961), 43-55.
'•Chomsky N., Three models for the description of language, /. R. E.
Trans. PG1T 2 A956), 113—124. (Русский перевод: Хомский Н., Три
модели для описания языка, Кибернетический сборник, вып. 2, ИЛ,
"¦Chomsky N., On certain formal properties of grammars, Information
and Control, 2 A959), 137—267. (Русский перевод: Хомскнй К,
О некоторых формальных свойствах грамматик, Кибернетический
9 с i,060*""' Dun- 5- ИЛ' 1962- СТР- 279—312.)
•Chomsky N., A note on phrase structure grammars, Information and
Control, 2 A959), 393—395. (Русский перевод; Хомский К, Заметки
0 грамматиках непосредственных составляющих. Кибернетический
сборник, вып. 5, ИЛ, 1962, 312—315.)
Алгебраическая теория контекстно-свободных языков
241
V
Chomsky N., On the notion «Rule of Grammar», Proc. Symp. Applied
Math., 12. Am. Math. Soc. A961). (Русский перевод: Хомский Н.,
О понятии «правило грамматики», сб. Новое в лингвистике, вып. 4,
«Прогресс», 1965, стр. 34—65.)
Chomsky N., Context-free grammars and pushdown storage. Quarterly
Progress Reports, № 65, Research Laboratory of Electronics, M. I. T.,
1962.
Chomsky N., Formal properties of grammars. Handbook of Mathemati-
Mathematical Psychology, 2, ch. 12, Wiley, 1963, p. 323—418. (Русский перевод:
Хомский Н., Формальные свойства грамматик, Кибернетический
сборник, вып. 2, «Мир», 1966, стр. 121—230.)
Chomsky N., The logical basis for linguistic theory, Proc. IX-th Int.
Cong. Linguists A962). (Русский перевод: Хомский Н„ Логические
основы лингвистической теории, сб. Новое в лингвистике, вып. 4,
«Прогресс», 1965, стр. 465—575.)
С h о m s k у N., Miller G. A.. Finite state languages, Information and
Control, 1 A958), 91—112. (Русский перевод: Хомский Н., Мил-
Миллер Д., Языки с конечным числом состояний, Кибернетический сбор-
сборник, вып. 4, ИЛ, 1962, стр. 231—255.)
С h о m 5 k у N., Miller G. A., Introduction to the formal analysis of
tl l A962) Hdbk f Mthtil Phl l
14.
15.
24.
25.
26.
27,
h о 5 k у N., Miller G. A., Introduction to the formal analysis of
natural languages, A962) Handbook of Mathematical Psychology, vol.
2, Ch. 12, Wiley, 1963, 269—322. (Русский перевод: Хомский Н.,
М н л л е р Дж., Введение в формальный анализ естественных языков,
Кибернетический сборник, вып. 1, «Мир», 1965, стр. 229—290.)
Davis M., Computability and unsolvability, New York, McGraw-Hill,
1958.
E 1 g о t С. С, Decision problems of finite automata design and related
arithmetics, Trans. Am. Math. Soc, 98 A961), 21—51.
G i n s b u r g S., Rice H. G., Two families of languages related to
ALGOL, Technical Memorandum, Systems Development Corporation,
Sante Monica, California, 1961.
Gins burg S., Rose G. F., Operations which preserve definability in
languages, Technical Mamorandum. Systems Development Corporation,
Santa Monica, California, 1961.
J u n g e n R. Sur les series de Taylor n'ayant gue des singularites algeb-
rico — logarithmiques sur leur cercle de convergence, Comm. Math.
Helvetia, 3 A931), 286—306.
K'eene S. C, Representation of events in nerve nets and finite auto-
automata. Automata Studies, Princeton, 1956, 3—41. (Русский перевод:
К л и н и С. К-, Представление событий в нервных сетях и конечных
автоматах, сб. «Автоматы», ИЛ, 1956, стр. 15—67.)
Кулагина О. С, Об одном способе определения грамматических по-
нятий, сб. «Проблемы кибернетики», вып. 1, Физматгнз, 1958, стр. 203—
214.
L a m b e k J., The mathematics of sentence structure, Am. J, Math., 65
A958), 153—170. (Русский перевод: Ламбек И., Математическое
исследование структуры предложений, сб. «Математическая лингви-
лингвистика», «Мир», 1964, стр. 47—68.)
L a m b e k J., On the calculus of syntactic types, Proc. Symposium Ap-
Applied Math., 12, Am. Math. Soc, 1961.
L у n d о n R. C, Equations in free groups, Trans. Am. Math. Soc, 96
A960), 445—457.
M с N a u g h t о n R., The theory of automata, To appear in Advances in
Computers, v. 2 (Academic Press).
M a h 1 e r K., On a theorem of Liouville ir fields of positive characteristic,
Canadian J. of Math., 1 A949), 397-400.

242
И. Хомский, М. П. Шютценбержв
/йЙМарков А. А., Об одной неразрешимой проблеме, ДАН СССР, 78
\-У A951), 1089—1092.
29. Miller G. A., Chomsky N., Finitary models of language users, Hand-
Handbook of Mathematical Psychology, 2, Wiley, 1963, 419—492.
30 M i n s k у М. L., Recursive unsolvability of Post's problem of Tag, Ann.
of Math., 74 A961), 437—455.
31. Myhill J., Linear bounded automata, WADD. Tech. Note, 60—165, Wright
Air Base, Ohio, 1960.
32. N e w e 11 A., S h a w J. C, Programming the logic theory machine, Proc.
Western Joint Computer Conference, 1957, 230.
33 Oettinger A. G., Automatic syntactic analysis and the pushdown sto-
store, Proc. of Symposia in Applied Math., 12, Am. Math. Soc, 1961.
34. Parikh R. J., Language generating devices, Quarterly Progress Report,
№ 60, Research Laboratory Electronics, M. I. T., 1961, 199—212.
35. P e r 1 e s M., Rabin M. O., Shamir E. The theory of definite auto-
automata, Tech. Report № 6, O. N. R., 1961.
36. Post E., A variant of recursively unsolvable problem. Bull. Amer. Math.
— Soc, 52 A946), 264—268.
C7JRabin M. O., Scott D., Finite automata and their decision problems,
^-^ /. В. М. Journal of Research, 3 A959), 115—125. (Русский перевод:
P а б н н М. О., Скотт Д., Конечные автоматы и задачи их разреше-
разрешения, Кибернетический сборник, вып. 4, ИЛ, 1962, стр. 58—91.)
38. R а п е у G. N., Functional composition patterns and power-series rever-
reversion, Trans. Am. Math. Soc, 94 A960), 441—451.
39. Ritchie R. W., Classes of recursive functions of predictable complexity,
Doctoral Diss. Dept. Math., Princeton U, 1960.
40. S с h e i n b e r g S., Note on the Boolean properties of context-free lan-
languages, Information and Control, 3 A960), 372—375.
41. Schiitzenberger M. P., On an application of semi-group methods,
/. R. E. Trans., IT2 A956), 47—60.
42. Schiitzenber ger M. P., Un probleme de la theorie de automates,
Seminaire Dubreil — Pisot (Paris), Dec, 1959.
43. Sch ii tz en b er ge r M. P., A remark on finite transducers, Information
and Control, 4 A961), 185—196.
44. Sch ii tz e n ber ger M. P., On the definition of a family of automata.
Information and Control, 4 A961), 245—270.
45. S с h ii t z e n b e r g e г М. P., Some remarks on Chomsky's context-free lan-
languages, Quarterly Progress Report № 68, Research Laboratory of Elect-
Electronics, M. f. Т., Oct. 1961, p. 155-170.
46. S с h ii t z e n b e r g e r M. P., On a theorem of R. Jungen, Proc Amer.
Math. Soc, 13 A962), 895—890.
47. S с h ii t z e n b e r g e r M. P., Finite counting automata, Information and
Control, 5 A962), 91—107.
48. Schutzenberger М. P., On context-free languages and pushdown
storage. To appear in IBM Journal of Research.
49. Schfltzenberger M. P. Certain elementary families of automata,
Symp. on mathematical theory of automata, Polytechnic Institute of
©Brooklyn, 1962.
Shepherdson J. C, The reduction of two-way automata to one-way
automata, /. В. М. Journal of Research, 3 A959), 198—200. (Русский
перевод: Шепердсон Дж. К., Сведение двусторонних автоматов к
односторонним автоматам, Кибернетический сборник, вып. 4. ИЛ,
1962, стр. 92—98.)
51. Shamir E.. On sequential languages, Tech. Report, 7, О. N. R., 1961.
S2.Yamada A., Counting by a class of growing automata, Doctoral Diss.,
Univ. of Penna, Philadelphia, I960,
СОДЕРЖАНИЕ
Математические вопросы
, А. А. Альберт. Конечные поля. Перевод Ю. Л. Сагаловича .... 7
Р. Г. Г а л л а г е р. Простой вывод теоремы кодирования и некоторые
применения. Перевод Б. С. Цыбакова 50
В. Л. И с т м е и. О построении/кодов без запятой. Перевод В. И. Ле-
венштейна ....,¦''. 91
Е. У. Карлайл. Приведенные формы для стохастических последова-
тельностных машин/Перевод Р. Г. Бухараева . 101
Е. Крейндлер. Развитие теории оптимальных по быстродействию про-
процессов управления. Перевод В. В. Глаголева Ill
Э. Р о к с и НуВ. С п и н а д ел. Достижимые эоны для автономных си-
систем дифференциальных уравнений. Перевод В. М. Яковлева . . .149
Математическая лингвистика
Н. Хомскнй, М. П. Шютценберже. Алгебраическая теория кон-
контекстно-свободных языков. Перевод Н. Г. Самойловой и Н. Г. Щер-
Щербаковой ,]95