\documentstyle[12pt,russcorr]{article}
\renewcommand{\refname}{Литература}
\hfuzz=1pt
\tolerance=1000
\emergencystretch=10pt
\def\BbbR{{\rm I\!R}} %reelle Zahlen
\def\BbbN{{\rm I\!N}} %natuerliche Zahlen
\def\BbbQ{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm
Q$}\hbox{\raise
0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}}
{\setbox0=\hbox{$\textstyle\rm Q$}\hbox{\raise
0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptstyle\rm Q$}\hbox{\raise
0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptscriptstyle\rm Q$}\hbox{\raise
0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}}}}
\def\BbbZ{{\mathchoice {\hbox{$\sf\textstyle Z\kern-0.4em Z$}}
{\hbox{$\sf\textstyle Z\kern-0.4em Z$}}
{\hbox{$\sf\scriptstyle Z\kern-0.3em Z$}}
{\hbox{$\sf\scriptscriptstyle Z\kern-0.2em Z$}}}}

\begin{document}

\centerline{Одно применение действительно-значной интерпретации
}
\centerline{грамматических рядов.
}
\medskip
\centerline{Ан.А.Мучник
}
\medskip
\centerline{Институт новых технологий. Москва
}
Приводимые  ниже  результаты  были  объявлены  в   [1].   Мы
используем  метод  работы  [2]  для  выделения   двух   семейств
контекстно-свободных  грамматик,  которые  в  некотором   смысле
полярны. Автор очень  признателен  Н.К.Верещагину  за  написание
предварительного текста настоящей статьи.

Контекстно-свободная   грамматика    задается    1)    двумя
непересекающимися  конечными  алфавитами ${V}_{N}$, ${V}_{T}$:  2)  конечным
набором правил вывода: 3) начальным символом из ${V}_{N}$.  Символы  из
алфавита ${V}_{N}$ будем называть нетерминалами, а символы из  алфавита
${V}_{T}$ --- терминалами. Каждое правило вывода имеет вид ${x}\longmapsto {u}$, где ${x}$
--- нетерминал, а ${u}$ --- слово  в  алфавите ${V}_{N}\bigcup {V}_{T}$.  Правило ${x}\longmapsto {u}$
позволяет заменить в любом слове любое вхождение  символа ${x}$  на
слово ${u}$. Будем  выводом  слова ${w}$  из  слова ${v}$  называть  любую
последовательность ${v}_{1},\ldots,
{v}_{n}$ слов в алфавите ${V}_{N}\bigcup {V}_{T}$,  в  которой
${v}_{1}={v}$, ${v}_{n}={w}$ и для каждого $i<n$ слово ${v}_{i+1}$ получается из слова ${v}_{i}$
применением одного из правил вывода грамматики. Слово ${w}$ выводимо
в грамматике, если оно выводимо из  начального  нетерминала  (то
есть однобуквенного слова,  состоящего  из  этого  нетерминала).
Языком, порождаемым грамматикой, называется множество всех  слов
в алфавите ${V}_{T}$, выводимых в грамматике.

Будем  называть  грамматику  приведенной,   если   выполнены
следующие требования:

1) каждый нетерминал входит в какое-нибудь выводимое слово:

2) из каждого  нетерминала  выводимо  какое-нибудь  слово  в
терминальном алфавите:

3) правая часть правила вывода не может состоять  из  одного
нетерминала:

4) правая часть правила вывода не бывает пустым словом.

Свойство грамматики быть приведенной,  очевидно,  разрешимо.
По любой грамматике  просто  построить  приведенную  грамматику,
порождающую тот же язык, кроме пустого слова, если оно  было  (в
приведенной грамматике пустое слово не выводимо из-за требования
4)).  Все  рассматриваемые  в  дальнейшем   контекстно-свободные
грамматики будем  предполагать,  если  не  оговорено  противное,
приведенными.

Каждой  грамматике  сопоставим  множество  деревьев  вывода.
Деревьями вывода будут конечные  корневые  деревья,  размеченные
символами из ${V}_{N}\bigcup {V}_{T}$. Сыновья  каждого  отца  линейно  упорядочены
``слева направо''. Все потомки более левого брата считаются  левее
всех потомков более правого. Понятие дерева вывода  определяется
индуктивно.

БАЗА. Дерево, состоящее из одного корня,  помеченного  начальным
нетерминалом, является деревом вывода.

ШАГ. Если ${T}$ --- дерево вывода, а ${l}$ --- какая-либо  концевая  вершина
(то есть лист), помеченная нетерминалом ${x}$, и в  грамматике  есть
правило вывода ${x}\longmapsto {a}_{1}\ldots
{a}_{n}$ $({a}_{i}\in {V}_{N}\bigcup {V}_{T})$, то  дерево,  получаемое
из ${T}$ приклеиванием к вершине $l$ $n$ веток, концы  которых  помечены
символами ${a}_{1},\ldots,{a}_{n}$ слева направо, является деревом вывода.

Размером дерева назовем количество его вершин, не являющихся
листьями (при этом, если дерево  состоит  из  одного  корня,  то
корень является одновременно  и  листом).  Будем  говорить,  что
дерево вывода ${T}$ есть дерево вывода  слова ${u}$,  если  при  чтении
слева направо пометок листьев ${T}$ получается ${u}$.  Очевидно,  слово
выводимо тогда и только тогда, когда оно имеет дерево вывода.

ЛЕММА 0. {\it В приведенной грамматике размер дерева вывода слова
${w}$ не превосходит числа ${2\cdot }{\rm длина}({w})-1$.}

ДОКАЗАТЕЛЬСТВО.  Индукция   по   размеру   дерева   вывода.
Предполагая  выполненность  утверждения  леммы  для  поддеревьев
растущих над сыновьями корня, просто получаем оценку  для  всего
дерева. Лемма~0 доказана.

ОПРЕДЕЛЕНИЕ. Грамматика называется однозначной, если  каждое
слово из порождаемого ею языка имеет ровно одно дерево вывода.

Чтобы сформулировать  основную  теорему,  привлечем  понятие
степенного ряда. Степенным рядом от (некоммутирующих) переменных
${{t}_{1},\ldots,
{t}_{m}}$  называется  формальная  сумма  вида ${\sum\limits_{w}w\cdot a(w)}$,  где ${w}$
пробегает множество всех слов в алфавите ${\{{t}_{1},\ldots,{t}_{m}\}}$, а ${a(w)\in {\BbbN}}$.
Степенные       ряды складываются        по        правилу
${\sum\limits_{w}w\cdot a(w)+\sum\limits_{w}w\cdot b(w)=\sum\limits_{w}w\cdot\Bigl(a(w)+b(w)\Bigr)}$  и  умножаются   по   правилу
${\left(\sum\limits_{w}w\cdot a(w)\right)\cdot \left(\sum\limits_{w}w\cdot b(w)\right)=\sum\limits_{w}\Bigl(w\cdot \sum\limits_{uv=w}a(u)\cdot b(v)\Bigr)}$ (внутренняя   сумма
берется  по  всем  парам  слов $u$, $v$  в   алфавите ${\{{t}_{1},\ldots,{t}_{m}\}}$,
конкатенация которых равна ${w}$).  Мы  будем  рассматривать  только
ряды с нулевым свободным членом, то есть такие ряды ${\sum\limits_{w}w\cdot a(w)}$, что
${a(\Lambda)=0}$. Заметим,  что  сумма  и  произведение  рядов  с  нулевым
свободным членом опять имеют нулевой свободный член.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Каждой грамматике, следуя  [2],  сопоставим  степенной  ряд,
переменными которого являются  терминалы  грамматики.  Этот  ряд
есть $\sum\limits_{w}w\cdot a(w)$,  где ${a(w)}$  равно  количеству  различных  деревьев
вывода в данной  грамматике  слова ${w}$  (это  количество  конечно
вследствие леммы~0). Если слово ${w}$  невыводимо,  то ${a(w)}$  равно
нулю. В силу приведенности  грамматики,  ряд $\sum\limits_{w}w\cdot a(w)$  не  имеет
свободного члена.

Метод  А.Л.Семенова,  изложенный  в  [2],  [3],  состоит   в
рассмотрении степенного ряда  грамматики  как  обычного  ряда  в
смысле математического анализа и подстановке  вместо  терминалов
положительных действительных  чисел.  Степенной  ряд  грамматики
является одной из  компонент  решения  некоторой  алгебраической
системы уравнений в степенных рядах, а сумма ряда при  значениях
терминалов из области сходимости удовлетворяет числовой  системе
уравнений, полученной из системы  на  ряды  подстановкой  вместо
терминалов их значений.

Приведем известную теорему ([3]) формализующую первую  часть
последнего  утверждения.  Приведем  также   ее   доказательство,
поскольку мы его будем использовать в дальнейшем.

ТЕОРЕМА 0. I. {\it Пусть ${r}_{i}({x}_{1},\ldots,{x}_{n})$  ---  степенные  ряды   от
переменных ${x}_{1},\ldots,{x}_{n},\,{t}_{1},\ldots,{t}_{m}$,  не  содержащие  членов  вида ${a}$
(свободных) и членов вида $a\cdot x_{j}$. Тогда система}
$$
\{x_{i}=r_{i}(x_{1},\ldots,x_{n})\mid i=1,\ldots,n\}\eqno ({\rm i})
$$
{\it имеет  единственное  решение  в  формальных  степенных  рядах   от
переменных ${t}_{1},\ldots,{t}_{m}$.}

II. {\it Пусть   дана   грамматика   с   нетерминалами
${x}_{1},\ldots,{x}_{n}$ и терминалами ${t}_{1},\ldots,{t}_{m}$. Сопоставим ей систему}
$$
\{x_{i}=u^{i}_{1}+\ldots+u^{i}_{k_{i}}\mid i=1,\ldots,n\}\eqno ({\rm ii})
$$
{\it где ${u}^{i}_{j}$ --- это правая часть правила вывода, $j$-ого среди тех, левая
часть которых есть ${x}_{i}$. Пусть, ${x}_{1}={s}_{1},\ldots,{x}_{n}={s}_{n}$ ---  решение  этой
системы\/}  (единственное  в  силу   пункта I   и   приведенности
грамматики). {\it Тогда ${s}_{i}$ есть ряд грамматики полученной из исходной
объявлением начальным нетерминалом ${x}_{i}$.}

ДОКАЗАТЕЛЬСТВО I.  Систему  (i)  можно  рассматривать   как
уравнение  на  нахождение  неподвижной  точки  оператора ${R}$  над
кортежами  из ${n}$  степенных  рядов  от   переменных ${t}_{1},\ldots,{t}_{m}$,
заданного равенством $R\langle s_{1},\ldots,{s}_{n}\rangle=
\langle {r}_{1}({s}_{1},\ldots,{s}_{n}),\ldots,{r}_{n}({s}_{1},\ldots,{s}_{n})\rangle$.    Определим    метрику    на
пространстве степенных рядов. Расстояние между $\sum\limits_{w}w\cdot a(w)$ и $\sum\limits_{w}w\cdot b(w)$
положим равным $2^{-l}$, где $l$ --- наименьшая длина такого слова ${w}$, что
${a(w)\neq b(w)}$.  Расстояние  между  кортежами  рядов  положим  равным
максимуму   расстояний   между   соответственными   компонентами
кортежей. Напомним, что мы рассматриваем только ряды  с  нулевым
свободным членом. Оператор ${R}$ сохраняет  это  свойство,  так  как
ряды ${r}_{i}$ не содержат свободных членов. Пользуясь отсутствием в ${r}_{i}$
членов вида ${a\cdot x}_{j}$, просто показать,  что ${R}$  является  сжимающим.
Поэтому оператор имеет единственную неподвижную точку.

II. Докажем вторую часть теоремы. Система (ii) есть  частный
случай системы (i).  Обозначим  через ${r}_{i}({x}_{1},\ldots,{x}_{n})$  {\sl многочлен},
стоящий в правой части $i$-го уравнения системы (ii).  Неподвижная
точка сжимающего оператора является пределом последовательности,
получаемой многократным применением оператора к любой  начальной
точке. В качестве начальной точки возьмем кортеж из одних нулей.
Тогда ${s}_{i}=\lim\limits_{\alpha\to \infty}s^{\alpha}_{i}$, где ${s}^{\alpha}_{i}$ обозначает $i$-ую  компоненту  результата
применения $\alpha $-ой итерации оператора к нулевому кортежу, то есть
$$
s^{0}_{i}=0\ ,\quad s^{\alpha+1}_{i}=r_{i}(s^{\alpha}_{1},\ldots,{s}^{\alpha }_{n}).
$$

Рассмотрим     также     последовательность      многочленов
$p^{\alpha}_{i}(x_{1},\ldots,{x}_{n})$, определенную равенствами
$$
p^{0}_{i}=x_{i}\ ,\quad p^{\alpha+1}_{i}=r_{i}(p^{\alpha }_{1},\ldots,p^{\alpha }_{n}).
$$

Очевидно, что $s^{\alpha}_{i}={p}^{\alpha}_{i}(0,\ldots,0)$.

Пусть\quad $({s},{w})$\quad  обозначает  коэффициент  ряда ${s}$   при   слове
${w\in \{x_{1},\ldots,x_{n},\,t_{1},\ldots,t_{m}\}^{*}}$. Индукцией по $\alpha $  просто  показать,  что
${(p^{\alpha}_{i},w)}$ равно количеству деревьев  вывода  размера  не  больше $\alpha $
слова ${w}$ из нетерминала ${x}_{i}$. Для этого надо  рассмотреть  правила
применяемые в корне дерева вывода.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Пусть $w\in \{t_{1},\ldots,t_{m}\}^{*}$. Нам надо доказать,  что $({s}_{i},{w})$  равно
количеству деревьев вывода ${w}$  из ${x}_{i}$.  Сходимость ${s}^{\alpha }_{i}$  означает
существование такого $A$, что при всех $\alpha \ge A\ ({s}_{i},{w})=({s}^{\alpha }_{i},{w})$. Так  как
${x}$-переменные не входят в ${w}$,  то $({s}^{\alpha }_{i},{w})=({p}^{\alpha }_{i},{w})$.  Следовательно,
размер деревьев вывода ${w}$ не превышает $A$, а их  количество  равно
$({p}^{A}_{i},{w})=({s}^{A}_{i},{w})=({s}_{i},{w})$.

Теорема~0 доказана.

Грамматика называется линейной, если правая часть каждого ее
правила  содержит  не  больше  одного  вхождения   нетерминалов.
Назовем нетерминал ${x}$ нелинейным,  если  из  него  можно  вывести
слово, содержащее не меньше двух вхождений ${x}$. Грамматику назовем
слабо линейной, если в ней нет нелинейных нетерминалов.

Грамматика называется сильно нелинейной, если она  порождает
бесконечный язык, и во всех выводах, кроме конечного  множества,
встречаются нелинейные нетерминалы.

Следующая   теорема   послужит   инструментом    дальнейшего
изучения. Областью изменения терминалов степенного ряда  считаем
пространство положительных действительных чисел.

ТЕОРЕМА 1. I. {\it У всякой  слабо  линейной  грамматики  область
сходимости ее степенного ряда открыта.}

II. {\it У всякой сильно нелинейной грамматики  область
расходимости ее степенного ряда открыта.}

ДОКАЗАТЕЛЬСТВО. I. Случай слабо линейной грамматики.

Скажем, что нетерминал ${y}$ следует из нетерминала ${x}$, если из ${x}$
выводимо  слово,   содержащее ${y}$.   Назовем   два   нетерминала
эквивалентными, если каждый из них следует  из  другого.  Теперь
введем  понятие  ранга  нетерминала.  Он  принимает  натуральные
значения.

ОПРЕДЕЛЕНИЕ. Нетерминал имеет ранг ${r}$, если он не имеет ранга
меньше ${r}$,  и  все  нетерминалы,  которые   следуют   из   него,
эквивалентны ему или имеют ранг меньше ${r}$.

Это является корректным определением индукцией по ${r}$  класса
нетерминалов ранга ${r}$. Очевидно,  что  эквивалентные  нетерминалы
имеют одинаковый ранг. Просто убедиться  в  следующих  свойствах
ранга:

1) Если в левой части  какого-то  правила  стоит  нетерминал
ранга ${r}$, то в его  правую  часть  не  входят  нетерминалы  ранга
больше ${r}$.

2) Если в левой части какого-то правила стоит нетерминал ${x}$,
а в его правую часть входит нетерминал ${y}$ равного ранга, то ${x}$ и ${y}$
эквивалентны.

В слабо линейной грамматике выполнено еще одно свойство.

3) Если в левой части  какого-то  правила  стоит  нетерминал
ранга ${r}$, то в  его  правой  части  не  больше  одного  вхождения
нетерминалов ранга ${r}$.

Можно определить слабо линейные грамматики,  как  грамматики
удовлетворяющие свойству 3). Это было бы равносильное  исходному
определение.

Нам нужно доказать, что область сходимости  ряда  грамматики
открыта. Для этого используем теорему~0,  по  которой  этот  ряд
удовлетворяет системе (ii).

В  случае  линейной  грамматики  система  (ii)  состоит   из
линейных по  нетерминалам  уравнений.  В  случае  слабо  линеной
грамматики  система  (ii)  распадается   на   несколько   почти
линейных систем.  Именно,  если  рассмотреть  отдельно  систему
уравнений,  левые  части  которых  имеют  ранг ${r}$,  и  при  этом
нетерминалы  ранга  меньше ${r}$  считать  известными  рядами,   то
получится линейная система.

Будем решать систему (ii) следующим образом.  Сначала  решим
систему, составленную из уравнений с левыми частями ранга 0. Это
линейная система. Затем решим систему, составленную из уравнений
с левыми частями ранга 1. Это будет снова  линейная  система,  в
коэффициенты которой входят степенные ряды,  уже  найденные  для
нетерминалов ранга 0. И так далее.

Назовем степенной  ряд  хорошим,  если  выполнены  следующие
условия (напомним, что мы рассматриваем только  ряды  с  нулевым
свободным членом,  и  что  область  изменения  их  переменных  ---
положительные действительные числа):

0) все коэффициенты ряда неотрицательны:

1) область сходимости  ряда  может  быть  выделена  системой
рациональных  строгих  неравенств  (то  есть   неравенств   вида
${f(t_{1},\ldots,t_{m})/g(t_{1},\ldots,t_{m})>0}$, где ${f}$ и ${g}$ --- многочлены  с  целыми
коэффициентами):
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
2) на области сходимости сумма ряда выражается  рациональной
функцией от $t_{1},\ldots,t_{m}$.

Заметим, что ряд равный переменной является хорошим.

ЛЕММА 1. {\it Пусть имеется система в степенных рядах}
$$
\{x_{i}=b_{i}+\sum_{j}a_{ij}x_{j}\}\eqno ({\rm iii})
$$
{\it в которой все ${b}_{i}$ и ${a}_{ij}$ --- хорошие ряды.}

\noindent {\it Тогда эта система имеет единственное решение $\{{s}_{i}\}$, причем все ${s}_{i}$
--- хорошие ряды.}

ДОКАЗАТЕЛЬСТВО. То, что система имеет единственное  решение,
следует из теоремы~0. Более того, по известной теореме  из  [3],
решения ${s}_{i}$ системы (iii) могут быть получены из ее коэффициентов
$b_{i}$, $a_{ij}$  с  помощью  конечного  количества   операций   сложения,
произведения и итерации  степенных  рядов.  Операция  итерации~$*$
применима только к степенным рядам с нулевым свободным членом  и
определяется равенством ${s}^{*}={s}+{s}^{2}+{s}^{3}\ldots$.

Указанная  теорема  о  решении  линейной  системы   является
простым обобщением теоремы S.C.Kleene о регулярности  автоматных
множеств.

Нам нужно доказать, что ${s}_{1},\ldots,s_{n}$ --- хорошие  ряды.  Докажем,
что сумма,  произведение  и  итерация  хороших  рядов,  являются
хорошими рядами. С условием 0) все очевидно. Проверим 1) и 2).

СУММА. Область сходимости суммы рядов ${p}+{q}$  есть  пересечение
областей сходимости рядов ${p}$  и ${q}$,  так  как  ввиду  условия  0)
значения  всех  мономов  неотрицательны.  Пересечение   областей
соответствует объединению задающих их систем неравенств.\\
Сумма ряда ${p}+{q}$  равна  сумме  суммы  ряда ${p}$  и  суммы  ряда ${q}$,
следовательно есть рациональная функция.

ПРОИЗВЕДЕНИЕ. Если один из рядов  тождественно  нулевой,  то
выполненность условий 1) и 2) очевидна.

\noindent Иначе,  область  сходимости  опять  есть  пересечение   областей
сходимости, а сумма ряда ${p\cdot q}$ равна произведению суммы ряда ${p}$  на
сумму ряда ${q}$.

ИТЕРАЦИЯ.  Область  сходимости  ряда ${r}^{*}$  задается  системой
рациональных неравенств, выделяющих область сходимости ряда ${r}$, к
которой добавлено неравенство ${\rm sum}(r)<1$.

\noindent Сумма ряда ${r}^{*}$ равна ${\rm sum}(r)/(1-{\rm sum}(r))$.

Лемма~1 доказана.

Заметим,  что   когда   переменные   ряда   интерпретируются
действительными числами, порядок  сомножителей  в  произведениях
становится неважным. Заметим также, что перестановки  переменных
в мономах правых частей системы~(i) приводят к перестановкам  же
переменных в мономах решений.

Докажем,   что   при   решении    подсистем    системы~(ii),
соответствующих последовательным значениям ранга нетерминалов  в
левых частях уравнений,  решаемые  системы  будут  удовлетворять
посылкам  леммы~1.  Рассуждаем  индукцией  по  рангу.  Очередная
подсистема приводится к виду (iii) перестановками  сомножителей.
При  этом  коэффициенты ${b}_{i}$, ${a}_{i,j}$  получаются   умножениями   и
сложениями из терминалов и решений предыдущих подсистем.

Для доказательства теоремы в слабо линейном случае  осталось
заметить, что область выделяемая системой  строгих  рациональных
неравенств открыта.

II. Случай сильно нелинейной грамматики.
\par
Пусть ${s}_{i}({t}_{1}\ldots {t}_{m})$  обозначает  ряд,  являющийся   значением
неизвестного ${x}_{i}$ в решении системы~(ii).  Пусть ${x}_{1}$  ---  начальный
нетерминал и точка $({c}_{1}\ldots {c}_{m})$  принадлежит  области  расходимости
ряда ${s}_{1}({t}_{1}\ldots {t}_{m})$.

Нам полезно доказать следующие утверждения.

1)  Существует  нелинейный  нетерминал ${x}_{i}$,   для   которого
числовой ряд ${s}_{i}({c}_{1}\ldots {c}_{m})$ расходится.

2)  Область  расходимости  всякого  нелинейного  нетерминала
открыта.

Выведем из этих двух утверждений  существование  окрестности
точки $(c_{1}\ldots c_{m})$, во всех точках которой ряд ${s}_{1}$ расходится.

Пусть ${x}_{i}$  нелинейный  нетерминал  с  расходящимся  в  точке
$(c_{1}\ldots c_{m})$ рядом. Так как ${x}_{i}$ следует из  начального  нетерминала,
то для некоторого $\alpha $ многочлен ${p}^{\alpha }_{1}({x}_{1}\ldots {x}_{n})$ нефиктивно зависит  от
${x}_{i}$ (многочлены ${p}^{\beta }_{j}$  и  оператор ${R}$  определены  в  доказательстве
теоремы~0). Докажем индукцией по $\beta $, что при $j=1\ldots n$  выполняется
${s}_{j}={p}^{\beta }_{j}({s}_{1}\ldots {s}_{n})$.  В  самом  деле, ${p}^{\beta }_{j}$  можно  рассматривать  как
компоненты  оператора $R(R(R\ldots))$  ($\beta$ раз).  Неподвижные  точки
оператора ${R}$  неподвижны  для   его   степеней.   В   частности,
${s}_{1}={p}^{\alpha }_{1}({s}_{1}\ldots {s}_{n})$.  Из  свойства  2)  приведенности  грамматики  и
теоремы~0(II) следует, что у  каждого  ряда ${s}_{j}$  есть  ненулевой
коэффициент, а значит его сумма в любой точке  с  положительными
координатами  положительна.   Ряд ${s}_{i}$   нефиктивно   входит   в
${p}^{\alpha }_{1}({s}_{1}\ldots {s}_{n})$,   и,    благодаря    отмеченной    положительности,
${p}^{\alpha }_{1}({s}_{1}\ldots {s}_{n})\ (=s_{1})$ расходится там, где расходится ${s}_{i}$.

Итак, докажем, что существует нелинейный нетерминал ${x}_{i}$,  для
которого числовой ряд ${s}_{i}({c}_{1}\ldots {c}_{m})$ расходится. Благодаря  сильной
нелинейности достаточно построить длинный  вывод,  в  котором  у
всех применяемых правил  в  левых  частях  стоят  нетерминалы  с
расходящимися  в  точке ${c}_{1}\ldots {c}_{n}$  рядами.  Вывод  начинается   с
нетерминала ${x}_{1}$.      Из      системы       (ii)       имеем
${s}_{1}={u}^{1}_{1}({s}_{1}\ldots {s}_{n})+\ldots+{u}^{1}_{k}({s}_{1}\ldots {s}_{n})$. Значит, хотя бы один  из  рядов
${u}^{1}_{j}({s}_{1}\ldots {s}_{n})$ расходится в точке ${c}_{1}\ldots
{c}_{m}$ (скажем при $j=j_{1}$). Далее,
хотя бы одному нетерминалу, входящему в ${u}^{1}_{j_{1}}$,  соответствует  ряд
расходящийся в точке ${c}_{1}\ldots {c}_{m}$. К этому  нетерминалу  (скажем ${x}_{2}$)
применим  те  же  рассуждения,  что  и  к  начальному.  Повторяя
описанную  процедуру  много  раз,  мы  получим  искомый   вывод:\\
${x}_{1}\longmapsto {u}^{1}_{j_{1}}$, ${x}_{2}\longmapsto \ldots\ $.

Теперь  докажем,  что  область  расходимости  ряда   всякого
нелинейного  нетерминала  открыта.   Пусть ${x}_{i}$   ---   нелинейный
нетерминал,  и  ряд ${s}_{i}$  расходится  в   точке $(c_{1}\ldots {c}_{m})$.   По
определению нелинейности нетерминала для некоторого $\alpha $  многочлен
${p}^{\alpha }_{i}({x}_{1}\ldots
{x}_{n})$ имеет одночлен, содержащий не меньше двух  вхождений
${x}_{i}$.  Как  мы  уже  заметили, ${s}_{i}={p}^{\alpha }_{i}({s}_{1}\ldots
{s}_{n})$  (для   всех $\alpha $).
Перестановка сомножителей приводит к равенству ${s}_{i}={s}^{2}_{i}{p}({s}_{1}\ldots
{s}_{n})+{q}({s}_{1}\ldots
{s}_{n})$, где ${p}$ и ${q}$ некоторые многочлены, причем ${p}$  ненулевой
многочлен.  Пусть  положительное  число $\sigma $  меньше  суммы   ряда
${p}({s}_{1}\ldots {s}_{n})$  в  точке $(c_{1}\ldots c_{m})$   (сумму   расходящегося   ряда
подразумеваем  равной  $+\infty$).  Пользуясь  непрерывностью,  возьмем
такую окрестность ${U}$  точки $(c_{1}\ldots {c}_{m})$,  в  которой  сумма  ряда
${p}({s}_{1}\ldots
{s}_{n})$ везде  больше $\sigma/2$.  Поскольку  ряд ${s}_{i}$  в $(c_{1}\ldots {c}_{m})$
расходится, в некоторой окрестности ${V}$ этой точки сумма ${s}_{i}$  везде
больше $4/\sigma$. Покажем, что в ${U\bigcap V}$ ряд ${s}_{i}$ расходится.  Рассмотрим  в
указанной окрестности точку, сумму ряда ${s}_{j}$ в ней обозначим через
${s}^{+}_{j}$. Тогда ${s}^{+}_{i}=(s^{+}_{i})^{2}{p}({s}^{+}_{1}\ldots
{s}^{+}_{m})+{q}({s}^{+}_{1}\ldots {s}^{+}_{m})$. Из ${p}({s}^{+}_{1}\ldots
{s}^{+}_{m})>\sigma/2$ и
${s}^{+}_{i}>4/\sigma$ следует ${s}^{+}_{i}>(4/\sigma)^{2}\cdot \sigma/2=8/\sigma$.  Но  тогда ${s}^{+}_{i}>(8/\sigma)^{2}\cdot
\sigma/2=32/\sigma$. И так до бесконечности.

Теорема~1 доказана.

ТЕОРЕМА 2.  {\it Каждое  из  свойств  грамматики  ---  быть   слабо
линейной, быть сильно нелинейной --- разрешимо.}

ДОКАЗАТЕЛЬСТВО.  Сначала   докажем   разрешимость   свойства
нелинейности нетерминала. Для этого  оценим  минимальный  размер
дерева  вывода  (если  оно  есть)  из   нетерминала ${x}$   слова,
содержащего два (как минимум) вхождения ${x}$.  Ветвление  деревьев
вывода ограничено длиной правых частей правил  вывода.  Остается
оценить высоту минимального  дерева.  Рассмотрим  в  дереве  две
ветви $\pi_{1}$  и $\pi_{2}$,  ведущие  из  корня  в  листья,  помеченные ${x}$.
Предположим, что длина некоторой ветви дерева больше  утроенного
числа нетерминалов. Разобъем эту ветвь  на  три  части:  участок
общий и с $\pi _{1}$ и с $\pi _{2}$, участок общий  только  с  одной  из  ветвей
$\pi _{1}$, $\pi _{2}$ и остальной участок. Длина одного из участков должна  быть
больше  числа  нетерминалов.  На   этом   участке   какой-нибудь
нетерминал повторяется  дважды  (скажем,  в  вершинах $\gamma $  и $\delta $).
Заменим поддерево, растущее над $\gamma $, на поддерево, растущее над $\delta $.
Пометки нетерминалом ${x}$ корня и двух листьев при этом сохранятся.
Если $\gamma $ ниже $\delta $, то размер дерева уменьшится. Противоречие.

Назовем нетерминал циклическим, если из него выводимо слово,
содержащее  его  и  не   равное   ему.   Разрешимость   свойства
цикличности  нетерминала  доказывается  аналогично   предыдущему
абзацу.  В  выводе   достаточно   длинного   слова   обязательно
встречается   циклический   нетерминал.   Действительно,   ввиду
ограниченности степени ветвления деревьев вывода, длинное  слово
не может иметь  низкого  дерева  вывода.  На  длинной  же  ветви
какой-либо нетерминал встретится дважды.

Грамматика порождает бесконечный язык тогда и только  тогда,
когда она имеет циклический нетерминал. ``Только тогда''  доказано
в предыдущем  абзаце.  ``Тогда''  просто  следует  из  определений
цикличности нетерминала и приведенности грамматики.

Теперь несложно показать, что  грамматика  сильно  нелинейна
тогда и только тогда, когда в ней есть циклический нетерминал  и
нет дерева вывода, которое содержит циклический нетерминал и  не
содержит нелинейных нетерминалов. Минимальная  высота  дерева  с
последним свойством (если оно есть) очевидно не превышает  числа
нетерминалов.

Теорема~2 доказана.

Сделаем  простые  замечания  о  линейности  и  нелинейности.
Линейность влечет  слабую  линейность,  которая  несовместима  с
сильной нелинейностью.  Однако,  линейная  и  сильно  нелинейная
грамматики  могут  порождать  один  и  тот  же  язык.  Например,
множество всех непустых слов в алфавите $\{a\}$ порождается линейной
грамматикой ${\{\,{x}\longmapsto {ax}\,,\,{x}\longmapsto {a}\,\}}$  и  грамматикой,  полученной  из
предыдущей  добавлением  правила ${x}\longmapsto {xx}$.  Понятно,  что   новое
правило  создает  возможность  выводить   одно   слово   многими
способами.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Язык,  порождаемый  однозначной   слабо   линейной   (сильно
нелинейной) грамматикой, будем называть языком со слабо линейной
(соответственно, сильно нелинейной) структурой.

ТЕОРЕМА 3.  {\it Семейство  однозначных  грамматик,   порождающих
языки со слабо линейной структурой, алгоритмически  отделимо  от
семейства однозначных  грамматик,  порождающих  языки  с  сильно
нелинейной структурой.}

ДОКАЗАТЕЛЬСТВО.  Алгоритмически    разрешимое    свойство,
отделяющее первое семейство от второго, --- это открытость области
сходимости степенного ряда грамматики. Надо  доказать,  что  это
свойство   действительно   отделяет   семейства   и   что    оно
алгоритмически разрешимо.

Пусть грамматика ${G}_{1}$ однозначна и порождает язык ${L}$  со  слабо
линейной структурой. Тогда в силу  однозначности,  ее  степенной
ряд  есть $\sum\limits_{w\in L}w\cdot 1$.  Кроме  того,  существует  однозначная  слабо
линейная грамматика ${G}_{2}$, порождающая ${L}$. Степенной ряд ${G}_{2}$ есть так
же $\sum\limits_{w\in L}w\cdot 1$. По теореме~1 область сходимости этого  ряда  открыта,
что и требовалось доказать.

Пусть грамматика ${G}_{1}$ однозначна и порождает язык ${L}$  с  сильно
нелинейной структурой. Ее степенной ряд $\sum\limits_{w\in L}w\cdot 1$ является в то  же
время степенным рядом некоторой сильно нелинейной грамматики ${G}_{2}$.
Следовательно, область расходимости ряда $\sum\limits_{w\in L}w\cdot 1$  открыта.  Ввиду
связности   пространства    пробегаемого    переменными    ряда,
одновременная открытость его областей сходимости и  расходимости
возможна только если одна из областей пуста.

Область сходимости  содержит  некоторую  окрестность  начала
координат. Действительно, число входящих в ряд мономов степени ${l}$
ограничено количеством слов длины ${l}$, то есть ${m}^{l}$, где ${m}$  ---  число
переменных. Значит ряд сходится, как геометрическая  прогрессия,
если все переменные меньше ${1/m}$.

Область расходимости содержит точку, все координаты  которой
равны 1. Это очевидно следует из бесконечности ${L}$.

Теперь  докажем  разрешимость  свойства   грамматики   иметь
открытую область сходимости степенного ряда.

ЛЕММА 2. {\it Пусть $(s_{1}\ldots {s}_{n})$ --- решение  системы  {\rm (ii)}.  Тогда  в
точке $(c_{1}\ldots {c}_{m})$ ряд ${s}_{1}$ сходится  тогда  и  только  тогда,  когда
числовая система, получаемая из системы {\rm (ii)} подстановкой вместо
${t}_{1},\ldots,{t}_{m}$ значений ${c}_{1},\ldots,{c}_{m}$,  имеет  решение  в  положительных
действительных числах.} (Напомним  соглашение  о  положительности
${c}_{1},\ldots,{c}_{m}$.)

ДОКАЗАТЕЛЬСТВО. Если ряд ${s}_{1}({c}_{1}\ldots {c}_{m})$ сходится, то и все ряды
${s}_{i}({c}_{1}\ldots {c}_{m})$   сходятся. Это   следует   из    рассуждений    в
теореме~1(II). Пусть ${s}^{+}_{i}$  есть  сумма  ряда ${s}_{i}({c}_{1}\ldots
{c}_{m})$.  Тогда
$({s}^{+}_{1}\ldots {s}^{+}_{n})$  является   положительным   решением   системы   (ii),
поскольку правила сложения и умножения  рядов  корректны,  когда
ряды сходятся.

Обратно, пусть ${s}_{1}({c}_{1}\ldots {c}_{m})$ расходится. Докажем, что числовая
система не имеет положительных решений. Предположим, $({s}^{+}_{1}\ldots
{s}^{+}_{n})$ ---
положительное решение  числовой  системы.  Пусть ${p}^{\alpha }_{i}({x}_{1}\ldots
{x}_{n})$  ---
многочлен, определенный в  доказательстве  теоремы~0.  Там  было
показано, что для всех $\alpha $ уравнение ${x}_{i}={p}^{\alpha }_{i}({x}_{1}\ldots{x}_{n})$  следует  из
(ii).  Обозначим  через ${q}^{\alpha }_{i}({x}_{1}\ldots
{x}_{n})$  многочлен,  получаемый  из
${p}^{\alpha }_{i}({x}_{1}\ldots
{x}_{n})$ подстановкой вместо  терминалов ${t}_{1},\ldots,{t}_{m}$  значений
${c}_{1},\ldots,{c}_{m}$.      Тогда      для      всех $\alpha $       выполнено
${s}^{+}_{1}={q}^{\alpha }_{1}({s}^{+}_{1}\ldots
{s}^{+}_{n})\ge {q}^{\alpha }_{1}(0\ldots 0)$.  Ряд ${s}_{1}$  есть  предел  многочленов
${p}^{\alpha }_{1}(0\ldots 0)$ в топологии степенных рядов. Ввиду  расходимости  ряда
${s}_{1}$ в точке $({c}_{1}\ldots
{c}_{m})$, из этого следует, что $\lim\limits_{\alpha\to\infty} q^{\alpha}_{1}(0\ldots 0)=\infty$. То
есть, ${s}^{+}_{1}\ge \infty$.

Лемма~2 доказана.

Теперь,  следуя  работе  [2],  воспользуемся   разрешимостью
элементарной теории упорядоченного  поля  действительных  чисел,
для  построения  алгоритма  распознавания   открытости   области
сходимости  степенного  ряда   грамматики.   Лемма~2   позволяет
выразить в указанной теории сходимость ряда грамматики  в  точке
заданной  индивидными   переменными.   После   этого   выражение
открытости не составляет проблемы.

Теорема~3 доказана.

В связи с приведенными  результатами  естественно  возникает
вопрос: не  является  ли  какое-нибудь  из  свойств  однозначной
грамматики --- быть слабо линейной или быть сильно  нелинейной
---  инвариантным;  то  есть,  например,  не   будет   ли   всякая
однозначная  грамматика,  порождающая  язык  со  слабо  линейной
структурой,   сама   слабо   линейной?   Ответ,   к   сожалению,
отрицателен. Язык всех непустых слов в  двухбуквенном  алфавите,
очевидно  имеющий  слабо  линейную  структуру,  можно   породить
однозначной грамматикой, не являющейся слабо линейной.

ТЕОРЕМА 4. {\it Грамматика $\{{\bf Л}\longmapsto {\bf Р}$, ${\bf Л}\longmapsto {\bf Д}$, ${\bf Л}\longmapsto {\bf ДЛ}$, ${\bf Р}\longmapsto {\bf у}$, ${\bf Р}\longmapsto {\bf уР}$,
${\bf Р}\longmapsto {\bf уД}$, ${\bf Р}\longmapsto {\bf уДР}$, ${\bf Д}\longmapsto {\bf л}$, ${\bf Д}\longmapsto {\bf уДД}\}$, где {\bf Л, Д, Р} --- нетерминалы, {\bf Л}  ---
начальный нетерминал, {\bf у,л}  ---  терминалы,  однозначна,  не  слабо
линейна и порождает язык всех непустых слов в алфавите $\{{\bf у},{\bf л}\}$.}

Замечание. Ради  большей  компактности  задания,  грамматика
содержит  правила  вида  нетерминал$\,\longmapsto\,$нетерминал.   Каноническое
преобразование грамматики в приведенную сохраняет  перечисленные
в теореме свойства.

ДОКАЗАТЕЛЬСТВО. Не слабо линейность очевидна.

Поясним  содержательный  смысл  рассматриваемой  грамматики.
Смысл нетерминалов  таков:  {\bf Д}  ---  это  ``бинарное  дерево'',  {\bf Р}  ---
``росток'', {\bf Л} --- ``лес''; смысл терминалов: {\bf у} --- ``узел'', {\bf л} --- ``лист''.

ОПРЕДЕЛЕНИЕ.  Деревом  (ростком)  назовем  всякое  слово   в
алфавите $\{${\bf у,л}$\}$,  которое  можно  вывести   из   нетерминала   {\bf Д}
(соответственно, {\bf Р}).

Геометрический образ дерева {\bf л} --- это одна точка. Если ${u}$ и ${v}$ ---
деревья,  то  в  геометрическом  образе  дерева  {\bf у}${uv}$  над  двумя
сыновьями корня растут геометрические образы ${u}$ и ${v}$.

Опишем синтаксический анализ произвольного  слова.  Пытаемся
отщепить слева от анализируемого слова дерево. Если это удалось,
то от оставшегося конца  слова  снова  пытаемся  отщепить  слева
дерево. И так делаем до тех пор, пока не останется пустое  слово
или росток.

Однозначность грамматики показывают следующие две леммы.

ЛЕММА 3. {\it Если одно дерево является началом другого  (говорим
в этом случае, что они согласованы), то они равны.}

ДОКАЗАТЕЛЬСТВО. Индукция по сумме длин двух деревьев.  Пусть
${u}$ и ${v}$ --- два согласованных дерева. Если одно из них однобуквенно,
то  утверждение  очевидно.  Иначе, ${u}$={\bf у}${u}_{1}{u}_{2}$   и ${v}$={\bf у}${v}_{1}{v}_{2}$,   где
${u}_{1}$, ${u}_{2}$, ${v}_{1}$, ${v}_{2}$ --- деревья.  Видим,  что ${u}_{1}$  и ${v}_{1}$  согласованы.  По
индуктивному предположению ${u}_{1}={v}_{1}$. Тогда ${u}_{2}$ и ${v}_{2}$ согласованы.  По
индуктивному предположению ${u}_{2}={v}_{2}$.  Следовательно, ${u}={v}$.  Лемма~3
доказана.

ЛЕММА 4. {\it Дерево не может быть началом  (даже  несобственным)
ростка.}

ДОКАЗАТЕЛЬСТВО. Индукция по длине ростка. Допустим ${w}={uv}$, где
${w}$ --- росток, а ${u}$ --- дерево. Анализируем росток.

Если ${w}=${\bf у}, утверждение очевидно.

Если ${w}=${\bf у}${z}$, то {\bf у}${z}={uv}$. Значит дерево ${u}$ представляется как {\bf у}${xy}$,
где ${x}$ и ${y}$ --- деревья. Следовательно, ${z}={xyv}$.

Если ${z}$  ---  росток,  получаем  противоречие  с   индуктивным
предположением.

Если ${z}$ --- дерево, то по лемме~3 ${z=x}$, и дерево ${y}$  оказывается
пустым, что невозможно.

Если $z=z_{d}{z}_{r}$, где ${z}_{d}$ --- дерево и ${z}_{r}$ --- росток, то ${z}_{d}{z}_{r}=xyv$ и по
лемме~3 ${z}_{d}={x}$.  Тогда ${z}_{r}={yv}$,  что  противоречит   предположению
индукции.

Лемма~4 доказана.

Следующая лемма показывает, что каждое непустое слово  может
быть выведено из начального нетерминала.

ЛЕММА 5. {\it Непустое  слово,  не  имеющее  начала,  являющегося
деревом, есть росток.}

ДОКАЗАТЕЛЬСТВО. Индукция по длине непустого слова ${u}$.

Если первая буква ${u}$ есть {\bf л}, то ${u}$ начинается с дерева.

Если ${u}=${\bf у}, то ${u}$ --- росток.

Если ${u}=${\bf у}${v}$, ${v}$ не пусто  и  не  начинается  с  дерева,  то  по
индуктивному предположению ${v}$ --- росток, и по определению ростка ${u}$
--- тоже росток.

Если ${u}=${\bf у}${v}$ и ${v}$ --- дерево, то по определению ${u}$ --- росток.

Пусть, ${u}=${\bf у}${vw}$  и ${v}$  ---  дерево.  Если ${w}$  ---  росток,  то  по
определению ростка ${u}$ --- тоже  росток.  Если  же ${w}$  начинается  с
дерева (скажем) ${z}$, то и ${u}$ начинается с дерева {\bf у}${vz}$.

Лемма~5 и теорема~4 доказаны.

Докажем, что свойство однозначной  грамматики  ``быть  сильно
нелинейной'' тоже не инвариантно.  А  именно  покажем,  что  язык
деревьев, порождаемый однозначной сильно нелинейной  грамматикой
$\{${\bf Д}$\longmapsto ${\bf л}, {\bf Д}$\longmapsto ${\bf у}{\bf Д}{\bf Д}$\}$, порождается также некоторой  однозначной  не
сильно нелинейной грамматикой.

ТЕОРЕМА 5.   {\it Грамматика $\{{\bf  Д}_{0}\longmapsto {\bf л}$,  ${\bf Д}_{0}\longmapsto {\bf у}{\bf Д}_{0}{\bf Д}_{0}$,    ${\bf Д}_{1}\longmapsto {\bf л}$,
${\bf Д}_{1}\longmapsto {\bf улД}_{1}$, ${\bf Д}_{1}\longmapsto {\bf ууД}_{0}{\bf Д}_{0}{\bf Д}_{0}\}$, где  {\bf Д}$_{0}$,  {\bf Д}$_{1}$  ---  нетерминалы,  {\bf Д}$_{1}$  ---
начальный нетерминал, {\bf у},{\bf л} ---  терминалы,  однозначна,  не  сильно
нелинейна и порождает язык деревьев.}

ДОКАЗАТЕЛЬСТВО. Нетерминал  {\bf Д}$_{1}$  очевидно  не  нелинеен.  Все
слова   вида   ({\bf у}{\bf л})$^{\beta }${\bf л}   выводимы   без   участия   {\bf Д}$_{0}$.   Поэтому
рассматриваемая грамматика не сильно нелинейна.

Ясно, что из {\bf Д}$_{0}$ выводятся в точности деревья. То, что из  {\bf Д}$_{1}$
выводятся только деревья, доказывается индукцией по выводу.

Покажем, что каждое дерево имеет единственный вывод  из  {\bf Д}$_{1}$.
Индукция по длине дерева ${u}$.

Если ${u}=${\bf л}, то ${u}$  очевидно  выводится  единственным  образом.
Иначе ${u}=${\bf у}${u}_{1}{u}_{2}$, где ${u}_{1},{u}_{2}$ --- деревья.

Если ${u}_{1}$={\bf л}, то вывод ${u}$ очевидно должен начинаться  с  правила
${\bf Д}_{1}\longmapsto {\bf улД}_{1}$. По индуктивному  предположению ${u}_{2}$  выводится  из  {\bf Д}$_{1}$
единственным образом.

Если ${u}_{1}\neq ${\bf л}, то ${u}_{1}=${\bf у}${v}_{1}{v}_{2}$, где ${v}_{1}$, ${v}_{2}$ --- деревья. В  этом  случае
вывод ${u}$ должен начинаться с правила ${\bf Д}_{1}\longmapsto {\bf ууД}_{0}{\bf Д}_{0}{\bf Д}_{0}$. Из  теоремы~4
мы знаем, что {\bf Д}$_{0}$ выводит каждое дерево единственным образом.

Теорема~5 доказана.

Результаты работы  [2]  и  наша  теорема~3  показывают,  что
однозначные грамматики обладают рядом ``хороших''  алгоритмических
свойств,  отсутствующих  в  семействе  всех  контестно-свободных
грамматик. Значение этого обстоятельства отчасти снижается  тем,
что,  как  известно,  свойство  грамматики  быть   однозначной
неразрешимо.   Все   же   ситуацию   можно   было   бы   считать
благоприятной,  если  бы  существовало  перечислимое   семейство
однозначных грамматик, члены которого порождают все  однозначные
языки.   Как   показывает    следующая    теорема,    доказанная
К.Ю.Горбуновым, это не так.

ТЕОРЕМА 6.  ([4]).  {\it Не  существует  перечислимого  семейства
контекстно-свободных    грамматик    (даже    не     обязательно
однозначных),  члены   которого   порождают   в   точности   все
однозначные языки.}

Вопрос о существовании такого  семейства  является  примером
проблемы  определенного  типа,  который   кажется   нам   весьма
интересным.  Пусть  задана   нумерация   какого-либо   семейства
объектов и выделено множество ${M}$  номеров  обладающих  ``хорошими''
алгоритмическими   свойствами.   Существует   ли    перечислимое
множество номеров из ${M}$, нумерующее то же подсемейство, что и ${M}$?

Автор думает, что массовая проблема  перечислить  множество
номеров из ${M}$, нумерующее то же  подсемейство,  что  и ${M}$  более
актуальна, нежели  обычно  рассматриваемая  проблема  разрешения
множества ${M}$.

\newpage
\centerline{ЛИТЕРАТУРА
}
\medskip
\noindent [1]~Мучник~Ан.А.~1985

Применение   метода    Семенова    к    анализу    структуры

контекстно-свободных языков.

Тезисы докладов и сообщений всесоюзной школы-семинара

``Семиотические   аспекты    формализации    интеллектуальной

деятельности. Кутаиси'',

сс.212-214, Москва.

\noindent [2]~Семенов~А.Л.~1973

Алгоритмические   проблемы    для    степенных    рядов    и

контекстно-свободных грамматик.

ДАН СССР, т.212, N1, сс.50-52.

\noindent [3]~Salomaa~A.,~Soittola~M.~1978

Automata --- theoretic aspects of formal power series.

Springer~-~Verlag

\noindent [4]~Горбунов~К.Ю.~1988

Об    одной    алгоритмической    проблеме    математической лингвистики.

Тезисы докладов и сообщений всесоюзной школы-семинара

``Семиотические   аспекты    формализации    интеллектуальной

деятельности. Боржоми'',

сс.8-11, Москва

\end{document}

