%22.03.2002
\documentclass{elsart}
\usepackage{amsfonts}

\begin{document}

\begin{frontmatter}
\title{One application of real-valued interpretation
of formal power series}

\author{An.A. Muchnik}
\address{Institute of New Technologies,
10 Nizhnyaya Radishewskaya, Moscow,  Russia, 109004}

\thanks{Fax: +7-095-915-69-63}
\thanks{The work was partially supported by grant N 01-01-00505
        of Russian Foundation for Basic Researches}


\begin{abstract}

We define two natural properties of context free  grammars.
The first property generalizes linearity and the second property
strengthens nonlinearity. A language generated  by  an
unambiguous grammar of the first type is called
the language with  weak linear  structure  and
a language  generated  by   an
unambiguous grammar of the  second  type is called
the  language with strong nonlinear structure.
Our main  theorem  states  that  the
family of unambiguous grammars  generating   languages  with
weak linear structure and the  family  of  unambiguous  grammars
generating  languages with  strong  nonlinear  structure  are
effectively separable.
\end{abstract}

\begin{keyword}
Context free grammars, context free languages, unambiguousness,
linearity.
\end{keyword}

\end{frontmatter}


\section{Introduction}

The results given below were announced in \cite{much} and
detailed in~\cite{much1}. We  use  the
method from \cite{sem} to define two families of context-free  grammars,
which are opposite in some sense.

Roughly speaking, a grammar  is  called  weak
linear if to each nonterminal we can assign a natural number
(called its rank) such that the right hand side $u$
of each rewriting rule $x\longrightarrow u$ has no
occurrence of a nonterminal with rank greater than ${\rm rank}(x)$
and has one or no occurrence of a nonterminal with rank equal to
${\rm rank}(x)$; a grammar is called strong nonlinear
if there are arbitrary long derivations and every sufficiently long
derivation includes some nonterminal $x$ such that
a word having at least two occurrences of $x$ can be derived from $x$.
Grammars are called ``weak linear'' and ``strong nonlinear''
because the first family properly includes
the family of all linear grammars
and the second family is properly included
in the family of all nonlinear grammars.


If we wish to study linearity and nonlinearity not as the
properties of grammars but as the properties of languages  then
it is natural to require the unambiguousness of  grammars.  For
example, the language of all words over the alphabet $\{{a},{b\}}$ can
be generated by the linear grammar
\[
 G=\{x\longrightarrow xa,\,x\longrightarrow xb,
     \,x\longrightarrow a,\,x\longrightarrow b\}
\]
and by the strong nonlinear grammar
${G\bigcup \{x\longrightarrow xx\}}$.
So in the following we shall consider unambiguous grammars only.
In some sense unambiguous grammar provides a structure
to the generated language (for instance, any language
generated by a linear unambiguous grammar has linear structure).
Our results are connected with the languages having weak  linear
or strong nonlinear structure. Our main Theorem~\ref{theor3} states
that we can effectively separate the family of unambiguous grammars
generating languages  with weak  linear  structure  from  the
family  of  unambiguous  grammars  generating  languages with
strong nonlinear structure.
The proof of this theorem uses Semenov's method (see \cite{sem}) of
substituting reals for terminals in the power
series of a grammar. Theorem~\ref{theor2} exhibits some
properties of power series of weak linear and  strong  nonlinear
grammars. These properties are used in the main theorem. Finally
we prove that the properties of an unambiguous  grammar  ``to  be
weak linear'' and ``to be strong  nonlinear''  are  not  invariant.
That is, there is an unambiguous grammar that isn't weak  linear
(strong nonlinear) and generates a  language  with  weak  linear
(strong nonlinear) structure (Theorems~\ref{theor4} and~\ref{theor5}).


\section{Preliminaries}

We begin with some well-known
facts from the theory of formal power series. The proofs of
them are used in the following.

A context-free grammar is a 4-tuple consisting of:
\begin{enumerate}
\item two disjoint finite alphabets $V_N$, $V_T$,
\item a finite set of rewriting rules,
\item an initial symbol from $V_N$.
\end{enumerate}

Symbols from $V_N$ are called  {\em nonterminals}, symbols
from $V_T$ are called {\em terminals}.

Each rewriting rule has the form $x\longrightarrow u$,
where $x$ is a nonterminal and $u$ is a word over $V_N\bigcup V_T$.

We say that a word $w_2$ {\em can be derived in one step from a
word $w_1$ by a rewriting rule\/} $x\longrightarrow u$
if $w_1$ and $w_2$ can be written as follows: $w_1=v_1xv_2$,
$w_2=v_1uv_2$, where $v_1$, $v_2$ are words.
A sequence $v_1,\ldots,v_n$ of words over $V_N\bigcup V_T$
is called a {\em derivation of a word $w$ from a word\/} $v$
if ${v}_{1}={v}$, ${v}_{n}={w}$, and
for each ${i<n}$ the word ${v}_{i+1}$ can  be
derived in one step from the word ${v}_{i}$ by some rewriting rule.
Any derivation from the initial nonterminal  (one letter word
containing the initial nonterminal) is called simply
{\em derivation}.

The grammar {\em generates a word\/} $w$ if $w$ can be derived from
the initial nonterminal. The set of all words over $V_T$ generated
by the grammar is called {\em the language generated by the grammar}.

A grammar is called {\em reduced\/} if:
\begin{enumerate}
\item Each nonterminal is a subword of some generated word.

\item\label{rgr:2} For each nonterminal there is some word over
             $V_T$ derived  from it.

\item The right hand side of any rewriting rule does not
             consist of only one nonterminal.

\item The right hand side of any rewriting rule is not empty.
\end{enumerate}

The property of a grammar  ``to  be  reduced''  is  obviously
decidable. Given a grammar we can construct a  reduced  grammar
that generates  the  same  language  except  the  empty  word.
(By condition~4 no reduced grammar generates the empty word.)

In the sequel we shall assume that all context-free grammars are
reduced (if it is not stated the contrary).

For each grammar let  us  consider  the  set of  {\em derivation
trees}. A derivation tree is a tree with root; its  vertices  are
marked by symbols from ${V}_{N}\bigcup {V}_{T}$.
The sons of each vertex are
linearly ordered ``from left to right''. All  the  descendants  of
``more left'' brother are considered to be ``more  left''  than  the
descendants of  all  ``more  right''  brothers.
The notion of a {\em derivation tree from a nonterminal} is defined by
induction.

BASE OF INDUCTION. A tree that contains only the root, which is marked
by a nonterminal, is a derivation tree from this nonterminal.

INDUCTION STEP. If ${R}$ is a derivation tree from a nonterminal ${y}$,
${l}$ is a leaf marked by a nonterminal ${x}$, and
the grammar contains a rewriting rule
${x}\longrightarrow {a}_{1}\ldots{a}_{n}$,
then the tree obtained from ${R}$ by adding ${n}$ edges
with begins in ${l}$ and with ends marked by
$a_1,\ldots,a_n$ from left to right is a derivation tree from $y$.

The {size} of a derivation tree is defined as the number of branching
vertices. If a tree consists of the root only then the root is
considered as a leaf. We say that $R$ {\em is a derivation tree\/}
of a word $u$ if $u$ can be obtained by reading the marks on
the leaves of $R$ from left to right. Derivation trees from the
initial nonterminal are called simply {\em derivation trees}.
Obviously, a word is generated iff it has a derivation tree.

\begin{lem}\label{lem0}
For  any  reduced  grammar  the  size   of   any
derivation tree of a word ${w}$ is not more than
$2\cdot {\rm length}(w)-1$.
\end{lem}
\begin{pf}
By  induction.  If the statement of the lemma holds for all
subtrees with roots in the sons of the root of a derivation tree,
then it is easily shown that the statement holds for the whole tree.
\end{pf}

To formulate the first theorem we  need  the  notion  of  a
formal power series. {\em A formal  power  series} (FPS), or simply
a power series, of (non-commuting) variables ${t_{1},\ldots,t_{m}}$ is
a formal sum ${a=\sum\limits_{w}w\cdot(a,w)}$,
where ${w}$ ranges over the set of  all  words  over
the alphabet ${\{t_1,\ldots,t_m\}}$, and ${(a,w)\in\Rset}$. We shall
say that ${(a,w)}$ is the {\em coefficient of $a$ on\/} $w$.
We define the sum of power series according to the rule
\[
\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)
\]
and the product of FPS according to the rule
\[
\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)
\]
(the notation ${uv=w}$ means that the concatenation of the words
$u$ and $v$ is equal to $w$).

We shall consider only series
$\sum\limits_w w\cdot(a,w)$ with  zero  constant term,
i.e., the series such that $(a,\Lambda)=0$, where $\Lambda$
stands for the empty word.
The sum and the product of such  series have zero constant terms too.

Following \cite{sem}, to each grammar assign FPS
$\sum\limits^{}_{{w}}{w\cdot }({a},{w})$, where variables are terminals
of the grammar and $(a,w)$ is equal to the number of different
derivation trees of the word ${w}$ (this number is finite due to
Lemma~\ref{lem0}).
If the grammar  does  not  generate  a  word ${w}$,  then $({a},{w})=0$.
Since the grammar is reduced, its FPS  has  zero  constant term. We
shall say that this FPS is the {\em formal power series of the grammar}.

A.~L.~Semenov suggested in \cite{sem} (see also \cite{sal})
to consider the FPS of a grammar as usual power series
in the sense of analysis and to substitute positive real numbers
for the terminals. Let us sketch this method.
The FPS of a grammar can be obtained from solution of some algebraic
system of equations, where unknowns range the set of all FPS.
If we substitute positive reals from the domain of FPS' convergence for
terminals in FPS and the system of equations,
then the sum of obtained numerical series satisfies
the obtained numerical system of equations.

The following well-known theorem (see \cite{sal}) formalizes the
previous statements. Its proof will be used in the sequel.

First let us introduce some notation.
Let $r$ be a power series in variables
$t_1,\ldots,t_m,x_1,\ldots,x_n$.
Let $s_1,\ldots,s_n$ be formal power series.
Let us substitute $s_1,\ldots,s_n$ for $x_1,\ldots,x_n$ in $r$.
Since $s_1,\ldots,s_n$ have no constant term
(recall that we consider FPS without constant term only),
the result is a new power series. Denote it by $r[s_1,\ldots,s_n]$.

Let $r_1,\ldots,r_n$ be power series in variables
$t_1,\ldots,t_m,\,x_1,\ldots,x_n$. Consider the equalities
\begin{equation}
x_i=r_i,\ i=1,\ldots,n \label{eq:i}
\end{equation}
as the system of equations with unknowns $x_1,\ldots,x_n$.
We say that a {\em solution\/} of~(\ref{eq:i}) is
a tuple ${\langle s_{1},\ldots,s_{n}\rangle}$ of FPS in variables
$t_1,\ldots,t_m$ if $s_i=r_i[s_1,\ldots,s_n]$ for all $i=1,\ldots,n$.
The main example of a system of this kind is the following.
Suppose that we have a (reduced) grammar with terminals
$t_1,\ldots,t_m$ and nonterminals $x_1,\ldots,x_n$.
Let $x_i\longrightarrow u^i_1,\ldots,x_i\longrightarrow u^i_{k_i}$
($i=1,\ldots,n$)\footnote{The symbol $i$ in $u^i$ is an index, not an exponent.}
be all rules with the left hand side $x_i$.
Evidently, the system
\begin{equation}
x_i=u^i_1+\ldots+u^i_{k_i},\ i=1,\ldots,n \label{eq:ii}
\end{equation}
has the form~(\ref{eq:i}).

\begin{thm}\label{theor0}
$ $\\
{\rm I.} Let for all $i$, $j$ no $r_{i}$ has terms of the form
$ax_j$, $a\neq 0$. Then the system~(\ref{eq:i}) has a unique solution.

{\rm II.} If $\langle s_1,\ldots,s_n\rangle$ is the solution of
the system~(\ref{eq:ii}) (unique according to part I),
then $(s_{i},w)$ is equal to the number of derivation trees of
$w$ from $x_i$ (for all $w\in\{t_1,\ldots,t_m\}^{*}$ and
for all $i=1,\ldots,n$).
\end{thm}
\begin{pf}
Let $i\in \{1,\ldots,n\}$ and let $s_1,\ldots,s_n$ be power series
(with zero constant term). As $r_i$ has no terms of the  form $ax_j$,
$a\neq 0$, coefficient of  the  series $r_i[s_1,\ldots,s_n]$ on any
word $w$ depends only on coefficients of $s_1,\ldots,s_n$ on the words
of length less than $|w|$ (by $|w|$ we denote the length of $w$). Thus
for all $w$ we have
\begin{eqnarray}
&\mbox{if }  (s_i,v)=(u_i,v)
\mbox{ for all }i
\mbox{ and for all } v
\mbox{ such that }|v|<|w| \nonumber\\
%
&\mbox{then } (r_i[s_1,\ldots,s_n],w)=
 (r_i[u_1,\ldots,u_n],w)
\mbox{ for all }i\,. \label{eq:1}
\end{eqnarray}

Now let us prove the part I of the theorem.

First let us prove the uniqueness of the solution of~(\ref{eq:i}).
Assume that power series $s_1,\ldots,s_n$; $u_1,\ldots,u_n$ of
variables $t_1,\ldots,t_m$ satisfy~(\ref{eq:i}), that is,
\begin{equation}
s_i=r_i[s_1,\ldots,s_n],\ i=1,\ldots,n \label{eq:2}
\end{equation}
and
\begin{equation}
u_i=r_i[u_1,\ldots,u_n],\ i=1,\ldots,n \label{eq:3}
\end{equation}
Let us prove that $\forall i\ s_{i}={u}_{i}$. Assume the contrary:
$\exists i\ s_{i}\neq {u}_{i}$. Denote by ${w}$ one of the shortest
words over $\{{t}_{1},\ldots,{t}_{m}\}$ such that there is
$i\in \{1,\ldots,n\}$ such that $({s}_{i},{w})\neq ({u}_{i},{w})$.
Then for all words ${v}$ of length less than $|w|$ and for all $i$
we have $(s_i,v)=(u_i,v)$. The implication~(\ref{eq:1}) combined
with~(\ref{eq:2}) and~(\ref{eq:3}) yields that $(s_i,w)=(u_i,w)$.
Contradiction.

Secondly let us prove the existence  of  solution  of  the
system~(\ref{eq:i}). We define a sequence of tuples
$\langle {s}^{\alpha }_{1},\ldots,{s}^{\alpha }_{n}\rangle,\
   \alpha \in \Nset$, where $s^\alpha_1,\ldots,s^\alpha_n$ are
power series of variables ${t}_{1},\ldots,{t}_{m}$,
by induction on $\alpha$.

BASE OF INDUCTION. $s^0_1=\ldots=s^0_n=0$

STEP OF INDUCTION. For each $i$
\[
{s}^{\alpha+1}_{i}={r}_{i}[{s}^{\alpha}_{1},\ldots,{s}^{\alpha}_{n}]
\]
We claim that for each $w\in \{t_{1},\ldots,{t}_{m}\}^{*}$,
each $i\in \{1,\ldots,n\}$, and each $\alpha \ge |w|$, $\beta \ge |w|$
it holds
\[
({s}^{\alpha }_{i},{w})=({s}^{\beta }_{i},{w})
\]
We prove this by induction on $|w|$. If $w=\Lambda$,
then $({s}^{\alpha }_{i},{w})=0$ for all $\alpha \in \Nset$,
because ${r}_{i}$ has no constant term.
Assume that $w\in \{t_{1},\ldots,{t}_{m}\}^{*},$ $|w|\ge 1$  and
our  assertion  holds  for  every ${v}$  such  that $|v|<|w|$.  Take
arbitrary $\alpha \ge |w|$, $\beta \ge |w|$. By induction hypothesis
$({s}^{\alpha-1}_{i},{v})=({s}^{\beta-1}_{i},{v})$ for all ${v}$ such
that $|v|<|w|$ and  all ${i}$. Thus~(\ref{eq:1}) involves that
$(s^\alpha_i,w)=(s^\beta_i,w)$ for all $i$.

Let $\langle s_1,\ldots,s_n\rangle$ be the ``limit'' of the sequence
${\langle s^\alpha_1,\ldots,s^\alpha_n\rangle}$. More precisely,
$(s_i,w)$ is the common value of $(s^\alpha_i,w)$, when $\alpha\ge|w|$.
Let us prove that $\langle s_1,\ldots,s_n\rangle$ is a solution
of~(\ref{eq:i}), that is, $s_i=r_i[s_1,\ldots,s_n]$, $i=1,\ldots,n$.
Take arbitrary $w\in\{t_1,\ldots,t_m\}^{*}$ and prove that
$(s_i,w)=(r_i[s_1,\ldots,s_n],w)$. Let us pick some $\alpha\ge |w|$.
Then
\[
(s_i,w)=(s^\alpha_i,w)=(r_i[s^{\alpha-1}_1,\ldots,s^{\alpha-1}_n],w)
\]
Using~(\ref{eq:1}), we get
\[
(r_i[s^{\alpha-1}_1,\ldots,s^{\alpha-1}_n],w)=(r_i[s_1,\ldots,s_n],w)
\]
This completes the proof of part I.

Let us prove part II. Denote by $r_i$ the power series
$u^i_1+\ldots+u^i_{k_i}$. As the grammar is reduced,
the system~(\ref{eq:ii}) satisfies the assumptions of part I.

Define the sequence
$\langle p^\alpha_1,\ldots,p^\alpha_n\rangle$
of tuples of power series
in variables $t_1,\ldots,t_m$,
$x_1,\ldots,x_n$ by the
equalities ${p}^{0}_{i}={x}_{i}$,
${p}^{\alpha+1}_{i}={r}_{i}[{p}^{\alpha}_{1},\ldots,{p}^{\alpha}_{n}]$.
And define also a corresponding sequence of derivation trees: each tree of 
level $0$ is a single vertex marked by a nonterminal ($x_i$); each tree of
level $(\alpha+1)$ is obtained from a tree of level $\alpha$ by applying
some rules to all nonterminals on the leaves. It is easy to prove 
(by induction) that if a tree of level $\alpha$ derives a word 
$w\in (V_N\bigcup V_T)^{*}$, then
length of $w$ is greater than $\alpha$. Hence if $w\in \{t_1,\ldots,t_m\}^{*}$,
then level $\alpha$ contains all derivation trees of $w$. Comparing the
definitions of $p^\alpha_i$ and $s^\alpha_i$ ($s^\alpha_i$ and $s_i$
are defined in the proof of part~I), we see that
$s^\alpha_i=p^\alpha_i[0,\ldots,0]$. Therefore for all
$w\in \{t_1,\ldots,t_m\}^{*}$ it holds $(s^\alpha_i,w)=(p^\alpha_i,w)$.
Let $\alpha=|w|$. 
Then $(s_i,w)=(s^\alpha_i,w)=
(p^\alpha_i,w)=($number of derivation trees of $w$ from $x_i$ of level
$\alpha)=($number of derivation trees of $w$ from $x_i)$.

Theorem~\ref{theor0} is proved.
\end{pf}

\section{Weak linear and strong nonlinear grammars: definition and
decidability}\label{sec3}

Recall that a grammar is called {\em linear\/} if the right hand side
of any rewriting rule  has  not  more  than  one  occurrence  of a
nonterminal. We say that a nonterminal $x$ is {\em nonlinear\/}
if some  word with at least two occurrences of ${x}$
can be derived from ${x}$.

\begin{defn}
A grammar is called {\em weak linear\/} if it does not have
nonlinear nonterminals.
\end{defn}

We say that a (finite) {\em quasiderivation\/} is any finite sequence
$x_1,x_2,\ldots,x_n$ of nonterminals such that $x_1$ is the initial
nonterminal and for every $i<n$ there is a rule $x_i\longrightarrow u$
such that $u$ has an occurrence of $x_{i+1}$.

\begin{defn}
A grammar is {\em strong nonlinear\/} if (1)~there  are
arbitrary long quasiderivations and (2)~every  sufficiently  long
quasiderivation has a nonlinear nonterminal.
\end{defn}

An {\em infinite quasiderivation\/} is any infinite  sequence
$x_1,x_2,\ldots,x_i,\ldots$ if all beginnings of it are
finite quasiderivations.

Due to Koenig's lemma we get an equivalent definition
of strong nonlinearity if we  say  that  there  is  an  infinite
quasiderivation  and  every  infinite  quasiderivation   has   a
nonlinear nonterminal.

Obviously, every  strong  nonlinear  grammar  generates  an
infinite language.

\begin{thm}\label{theor1}.
Both properties of a grammar, ``to be weak linear''
and ``to be strong nonlinear'', are decidable.
\end{thm}
\begin{pf}
To prove that the property  ``to  be  a  weak  linear
grammar'' is  decidable  it  is  sufficient  to  prove  that  the
property ``to be a nonlinear nonterminal'' is decidable.  To  this
end for a nonlinear nonterminal ${x}$ we estimate  the  minimal size of
derivation tree from ${x}$ having (at least) two leaves marked by $x$.
Obviously, the size is not greater than $N_s^{L_b}$, where
$N_s$ is the maximum number of sons of a vertex,
$L_b$ is the maximum length of a branch.
The number of sons of each vertex is bounded by the maximal length of
the right hand sides of rewriting rules. Let us fix two different
branches $\pi_1$ and $\pi_2$ of such derivation tree beginning in the
root and ending in leaves marked by $x$. Suppose that the length of
some branch $\pi$ of this derivation tree is greater than the tripled
number of nonterminals.  Let us divide this branch into three parts:
(1)~the part of $\pi$ common with both $\pi_1$ and $\pi_2$, (2)~the
part of $\pi$ common with only one branch $\pi_1$ or $\pi_2$ and
(3)~the remaining part of $\pi$. There is a part, whose length is
greater than the number of nonterminals. There is a nonterminal having
two occurrences in this part (say in vertices $\gamma$  and $\delta$).
Let us replace the subtree, whose root is $\gamma$, with the subtree,
whose root is $\delta$. The new derivation tree again  has  two  leaves
marked by ${x}$ and its root is also marked by ${x}$. If $\gamma $ is
lower in the tree than $\delta$, then size of the new tree is less than
size of the old one.

Let us prove the decidability of the  second  property.  To
this end we shall prove that both items in the definition of strong
nonlinearity are decidable.

Evidently, there are arbitrary long quasiderivations  iff
there is a quasiderivation having two occurrences  of  the  same
nonterminal. If such a quasiderivation exists, then there is such a
quasiderivation with the length not  more  than  the  number  of
nonterminals plus~1. Therefore we can decide  whether  there  is
such a quasiderivation.

In the same way we can prove that there are arbitrary  long
quasiderivations without nonlinear nonterminal iff  there  is  a
quasiderivation  with  length  not  more  than  the  number   of
nonterminals  plus~1  having  two  occurrences  of   the   same
nonterminal and having no nonlinear nonterminal.  Therefore  the
second item of the definition of a strong nonlinear  grammar  is
also decidable.

Theorem~\ref{theor1} is proved.
\end{pf}

Obviously, linearity implies weak linearity and weak linearity
is inconsistent with strong nonlinearity.

\section{Power series of weak linear and strong nonlinear grammars}

The following theorem is an important  tool  for  our  further
studies. In its formulation terminals are considered  to
range the set of positive real numbers.

\begin{thm}\label{theor2}
{\rm I.} For any  weak linear grammar the domain of its FPS convergence
is open.

{\rm II.} For any strong nonlinear grammar the domain  of  its FPS
divergence is open.
\end{thm}
\begin{pf}
I. Let us be given a weak linear grammar.

We say that a nonterminal $y$ {\em follows\/} a nonterminal ${x}$ if
some  word  that  contains ${y}$  can  be  derived  from ${x}$.   Two
nonterminals are called {\em equivalent\/} if they follow each other.

Let us define rank of nonterminals.
For each ${r\in \Nset}$ define the set $A_r$ of nonterminals by
induction: $A_0=\emptyset$, $A_{r+1}=$ (the set of all nonterminals
$x$ such that any nonterminal following $x$ belongs to $A_r$ or is
equivalent  to $x$). Evidently,
$A_0\subset A_1\subset A_2\subset\ldots$
and for every nonterminal $x$ there is $r$ such that
$x\in A_r$. The {\em rank\/} of a nonterminal ${x}$ is the least $r$
such that $x\in A_r$.

The reader can easily verify the following properties of the rank:

1) If the left hand side of some rewriting rule contains  a
nonterminal of rank ${r}$, then the right hand side does not contain
nonterminals of rank more than $r$.

2) If the left hand side of some rewriting rule contains
a nonterminal $x$ and the right hand side contains a nonterminal $y$ of
the same rank, then $x$ and $y$ are equivalent.

A weak linear grammar has one more property.

3) If the left hand side of some rewriting rule is a nonterminal
of rank $r$, then its right hand side cannot have the
form $uy_1vy_2w$, where $y_1$ and $y_2$ are (possibly  equal)
nonterminals of rank $r$.

We can define a weak linear grammar as a grammar
satisfying the third  property. The new  definition is
equivalent to the definition given in section~\ref{sec3}.

We must prove that the domain of convergence of grammar's power
series is open. According to theorem~\ref{theor0} the power series of
the grammar satisfies the system~(\ref{eq:ii}).

In the case of a linear grammar the system~(\ref{eq:ii}) consists  of
equations linearly depending on nonterminals. In the case of a
weak linear grammar the system~(\ref{eq:ii}) can be split into ``almost
linear'' systems. Namely, let us separately consider the  system
consisting of all equations with nonterminals of rank $r$ in the
left hand side; substitute certain power series for
the nonterminals of rank less than $r$; then we get a linear system.

Let us solve the system~(\ref{eq:ii}) in the following way.  First
let us solve the system consisting of all equations with the left
hand side having rank~1.  Secondly  let  us  solve  the  system
consisting of all equations with the left hand side having rank~2.
This system is also linear system (because we know the values of
all nonterminals of rank~1), its coefficients include
power series found in the previous step for nonterminals of
rank~1. And so on.

Let us call a power series  {\em good\/}  if  the  following  three
conditions hold (recall that we consider only series with zero constant
term and the range of variables is the set of positive reals):
\begin{enumerate}
\item\label{good0} all coefficients of the series are nonnegative;

\item\label{good1} the  domain of convergence of the series can be
specified by some system of strict rational inequalities
(in other words, inequalities of the form
$f(t_1,\ldots,t_m)/g(t_1,\ldots,t_m)>0$,
where $f$ and $g$ are polynomials  with integer coefficients);

\item\label{good2} within the domain of convergence the sum of the
series is a rational function of its variables.
\end{enumerate}

Note that any series consisting of a single  variable  is
good.

\begin{lem}\label{lem1}
Let
\begin{equation}
\{x_i=b_i+\sum^n_{j=1}a_{ij}x_j\,\colon\ i=1,\ldots,n\}\label{eq:iii}
\end{equation}
be a system in unknown FPS $x_1,\ldots,x_n$ and all $b_i$
and ${a}_{ij}$ be  good FPS.
Then this system has a unique solution
$\langle {s}_{1},\ldots,{s}_{n}\rangle$, where
all ${s}_{i}$ are good FPS.
\end{lem}
\begin{pf}
From Theorem~\ref{theor0} it follows that the system~(\ref{eq:iii}) has
a unique solution. Moreover the  well-known  theorem  from  \cite{sal}
states that solutions $s_i$ of the system~(\ref{eq:iii}) can be
obtained from its coefficients with a finite number of applying the
operations of sum, product and the binary operation
${p,q}\longrightarrow {p}^{*}\cdot {q}$.
The operation ${s}^{*}$ (or star-operation) can be applied to  FPS
with  zero  constant term only and is defined by the  equality
${p}^{*}=1+{p}+{p}^{2}+\ldots$.
Note that ${p}^{*}$ has nonzero constant  term  but ${p}^{*}\cdot {q}$
has zero constant term (if ${q}$ has zero constant term).

This theorem is a direct generalization of the well-known
theorem of Kleene on regularity of recognizable sets.

We must prove that $s_1,\ldots,s_n$ are good series. Let  us
prove that if ${p}$ and ${q}$ are good series, then ${p}+{q}$,
${p\cdot q}$, ${p}^{*}\cdot {q}$  are
again good series. The validity of the  condition~(\ref{good0}) for
${p}+{q}$, ${p\cdot q}$, ${p}^{*}\cdot {q}$ is evident. Let us verify
that ${p}+{q}$, ${p\cdot q}$, ${p}^{*}\cdot {q}$  satisfy~(\ref{good1})
 and~(\ref{good2}).

SUM. The domain of convergence of the series $p+q$ is
equal to the intersection of the domains of convergence of $p$ and
${q}$ because due to~(\ref{good0}) all terms are nonnegative. The
intersection of the domains corresponds to the union of systems
defining these domains.

The sum of series $p+q$ is equal to the  sum  of
series $p$ plus the sum of series $q$, consequently this sum is again
a rational function.

PRODUCT. If one of series  is  identically  zero, then  the
validity of~(\ref{good1}) and~(\ref{good2}) is evident.

In the other case the domain of convergence  is  again  the
intersection of the domains of convergence and the sum of series
${p\cdot q}$ is equal to the product of the sum of series ${p}$ and
the sum of series $q$.

ITERATION. The domain of convergence of series $r^*$  can  be
defined by the system defining the domain of convergence of $r$ and
the additional inequality ${\rm sum}(r)<1$.

The sum of series ${r}^{*}$ is equal to $1/(1-{\rm sum}({r}))$.

Lemma~\ref{lem1} is proved.
\end{pf}

Note that if we substitute reals for variables of FPS, then
the result of substituting doesn't depend on the order of multipliers
in terms.

Now recall that we solved system~(\ref{eq:ii}) sequentially and
considered the subsystems of~(\ref{eq:ii}) corresponding to a certain
rank of the left hand side. Let us prove by  induction  that all these
subsystems satisfy the assumptions of Lemma~\ref{lem1}.
Every subsystem can be reduced to the form~(\ref{eq:iii}) by
permutating multipliers in terms. And  the  coefficients
$b_i$, $a_{ij}$ are obtained from the terminals and the solutions of
the previous subsystems by  additions  and  multiplications. Note that
the solutions of the new system as functions from $\Rset^{m}$ into
$\Rset$ are equal to the solutions of the old system.

To complete the proof in the weak linear case it suffices to
note that any  set  defined  by  a  system  of  strict  rational
inequalities is open.

II. Suppose we have a strong nonlinear grammar.

Consider the system~(\ref{eq:ii}) associated with this grammar. Let
$\langle s_1,\ldots,s_n\rangle$ be the solution of~(\ref{eq:ii}).
Recall that ${s}_{i}$ is FPS of variables ${t}_{1},\ldots,{t}_{m}$,
where ${t}_{1},\ldots,{t}_{m}$ are the terminals of the grammar.
If ${c}_{1},\ldots,{c}_{m}$ are positive reals, then by
${s}_{i}({c}_{1},\ldots,{c}_{m})$ we denote the result of substituting
${c}_{1},\ldots,{c}_{m}$ for ${t}_{1},\ldots,{t}_{m}$
in ${s}_{i}$ (so
${s}_{i}({c}_{1},\ldots,{c}_{m})$ is a numerical series).

Let ${x}_{1}$ be the initial nonterminal and let
$({c}_{1},\ldots,{c}_{m})$  belong
to the domain of divergence of the series ${s}_{1}$.

The following assertions will be useful.

\begin{enumerate}
\item\label{asser1}
There exists a nonlinear nonterminal $x_i$ such that the
numerical series $s_i(c_1,\ldots,c_m)$ diverges.
\item\label{asser2}
For  every  nonlinear  nonterminal ${x}_{i}$  the  domain   of
divergence of the series ${s}_{i}$ is open.
\end{enumerate}

Let us  deduce  from  these  assertions  that  there  is  a
neighborhood of the point $({c}_{1},\ldots,{c}_{m})$ such that the
series $s_1$ diverges in all points of this neighborhood.

Let us fix some  nonlinear  nonterminal ${x}_{i}$  such  that $s_i$
diverges in $(c_1,\ldots,c_m)$. Because $x_i$ follows $x_1$, there is
$\alpha \in \Nset$
such that some term of ${p}^{\alpha }_{1}$ has an occurrence of $x_i$
(the  power series ${p}^{\beta }_{j}$, $\beta \in \Nset$,
$j=1,\ldots,{n}$, were defined in the proof of part II
of Theorem~\ref{theor0} by equalities
\[
{p}^{0}_{j}={x}_{j},\
{p}^{\beta+1}_{j}={r}_{j}[{p}^{\beta }_{1},\ldots,{p}^{\beta }_{n}],
\]
where $r_j$ stands for the right hand side of the $j$-th equation
in~(\ref{eq:ii})). Using induction, we can easily prove that for all
$\beta \in \Nset$ and for all $j=1,\ldots,n$
it holds ${s}_{j}={p}^{\beta }_{j}[{s}_{1},\ldots,{s}_{n}]$.

Hence ${s}_{1}={p}^{\alpha }_{1}[{s}_{1}\ldots {s}_{n}]$.
The condition~(\ref{rgr:2}) in the definition of reduced grammar and
Theorem~\ref{theor0} (part~II) imply that each power series
$s_j$ has a nonzero term. Therefore its sum is positive in every
point $(d_1,\ldots,d_m)$ such that $d_1>0,\ldots,d_m>0$.
The series $s_i$ occurs to some nonzero term of
$p^\alpha_1[s_1\ldots s_n]$, consequently
$p^\alpha_1(s_1\ldots s_n)\,(=s_1)$ diverges in every point, where
$s_i$ diverges.

Thus it remains to prove assertions~(\ref{asser1}) and~(\ref{asser2}).

Let us prove that there is a nonlinear nonterminal ${x}_{i}$  such
that the  series ${s}_{i}({c}_{1},\ldots,{c}_{m})$ diverges.
Due to the strong nonlinearity it is sufficient to construct an
infinite quasiderivation such that every nonterminal in it has
divergent series in the point $(c_1,\ldots,c_m)$.
This quasiderivation begins with the initial nonterminal $x_1$.
The system~(\ref{eq:ii}) yields
$s_1=u^1_1[s_1\ldots s_n]+\ldots+u^1_{k_1}[s_1\ldots s_n]$.
Thus there is $j$ such that $u^1_j[s_1\ldots s_n]$ diverges in
$(c_1,\ldots,c_m)$. Further, $u^1_j$ contains a nonterminal, whose
series diverges in $(c_1,\ldots,c_m)$. Let us apply the same reasoning
to this nonterminal (say $x_2$). Repeating this procedure,
we get the desired quasiderivation.

Let us now prove that the  domain  of  divergence  of  each
nonlinear nonterminal is open. Let ${x}_{i}$ be a nonlinear nonterminal
and let ${s}_{i}$ diverges in a point $({c}_{1},\ldots,{c}_{m})$.
By definition of the nonlinearity there is $\alpha$ such that
the series $p^\alpha_i$ has a term having at least two occurrences
of $x_i$. As mentioned above, $s_i=p^\alpha_i[s_1\ldots s_n]$
(for all $\alpha$). After some permutation of multipliers
we get $s_i=s^2_i\cdot p[s_1\ldots s_n]+q[s_1\ldots s_n]$, where $p$
and $q$ are power series with integer coefficients and $p$ isn't
identically zero. Let $\sigma $ be some positive number less than the
sum of the series ${p}[{s}_{1}\ldots {s}_{n}]$ in the point
${c}_{1},\ldots,{c}_{m}$ (the sum  of
the divergent series is considered to be equal  to $+\infty $). It is
easy to see that there is a neighborhood $U$ of $(c_1\ldots c_m)$ such
that in all its points ${p}[{s}_{1}\ldots {s}_{n}]$ is greater than
$\frac{\sigma}{2}$.  As  the series ${s}_{i}$ diverges in
$({c}_{1},\ldots,{c}_{m})$, there is a neighborhood $V$ of
$({c}_{1}\ldots {c}_{m})$ such that in all its points the sum of
${s}_{i}$  is  greater than $\frac{4}{\sigma}$. Let us prove that
in all points in ${U\bigcap V}$ the  series ${s}_{i}$
diverges. Let us take some point in ${U\bigcap V}$ and denote by $s^+$
sum of a series $s$ in this point. Then
$s^+_i=(s^+_i)^2 p[s_1\ldots s_n]^{+}+q[s_1\ldots s_n]^{+}$.
From ${p}[{s}_{1}\ldots {s}_{m}]^{+}>\frac{\sigma}{2}$  and
${s}^{+}_{i}>\frac{4}{\sigma}$ we can deduce that
$s^{+}_i>\left(\frac{4}{\sigma}\right)^2\cdot
               \frac{\sigma}{2}=\frac{8}{\sigma}$.
Therefore $s^{+}_i>\left(\frac{8}{\sigma}\right)^2\cdot
         \frac{\sigma}{2}=\frac{32}{\sigma}$. And  so on.

Theorem~\ref{theor2} is proved.
\end{pf}

\section{Languages with weak linear and strong nonlinear structure}

Recall that a grammar  is  called  {\em unambiguous\/}  if  every
generated word has a single derivation tree.

\begin{defn}
We shall say that a language has a {\em weak  linear\/}
({\em strong nonlinear\/}) structure if it can be generated by an
unambiguous weak linear (correspondingly strong nonlinear) grammar.
\end{defn}

\begin{thm}\label{theor3}
The  family   of   all   unambiguous   grammars
generating languages with weak linear structure and  the
family of all unambiguous grammars generating languages
with strong nonlinear structure are algorithmically separable.
\end{thm}
\begin{pf}
The following decidable property of a grammar separates these two
families: ``the domain of convergence of grammars FPS is open''.
We must prove that this property separates the families and
is decidable.

Let $G_1$ be an unambiguous grammar generating a language $L$ with weak
linear structure. As $G_1$ is unambiguous, its  power series is
$\sum\limits_{w\in L}w\cdot 1$. On the other hand, there is an
unambiguous weak linear grammar $G_2$ generating $L$. The formal power
series of $G_2$ is also $\sum\limits_{w\in L}w\cdot 1$. By
Theorem~\ref{theor2} the domain of convergence of this series is open,
q.e.d.

Let $G_1$ be an unambiguous grammar generating a language $L$ with
strong nonlinear structure. Let us prove that the domain of convergence
of its power series isn't open. Its power series
$\sum\limits_{w\in L}w\cdot 1$ is in the same time the power series
of an unambiguous strong nonlinear grammar $G_2$. Therefore the domain
of divergence of $\sum\limits_{w\in L}w\cdot 1$ is open. The range of
the variables of series is a connected region, consequently if the
domain of convergence of $\sum\limits_{w\in L}w\cdot 1$ is also open,
then one of these two domains is empty.

The domain of convergence includes a neighborhood of the point
$(0,\ldots,0)$. Indeed, an unambiguous series has not more than $m^l$
terms of length $l$ (where $m$ stands for the number of variables).
Hence the series converges if all variables are less than $1/m$
because it is less than a geometric progression.

The domain of divergence contains the point $(1,\ldots,1)$. This
follows from the infiniteness of $L$.

Let us prove now that given a grammar we can effectively decide
whether the domain of convergence of its power series is open.

Let us consider the system~(\ref{eq:ii}) for this grammar. Let
$c_1,\ldots,c_m$ be positive reals. Let $r_i$ stands for the right hand
side of the $i$-th equation in~(\ref{eq:ii}), that is,
$r_i=u^i_1+\ldots+u^i_{k_i}$. As $r_i$ has a finite number of terms
after substituting $c_1,\ldots,c_m$ for $t_1,\ldots,t_m$, we get
a power series with a finite number of terms in variables
$x_1,\ldots,x_n$. Let us denote this series by
${\bar r}_i[x_1,\ldots,x_n]$. We shall regard this series as
a polynomial of (commuting) variables $x_1,\ldots,x_n$. For every power
series $s$ of variables $t_1,\ldots,t_m$ with nonnegative coefficients
by ${\bar s}$ we denote the numerical series obtained by substituting
$c_1,\ldots,c_m$ for $t_1,\ldots,t_m$ in $s$ (the nonnegativeness of
coefficients provides that the convergence doesn't depend on the order
of terms).

\begin{lem}\label{lem2}
Let $\langle {s}_{1},\ldots,{s}_{n}\rangle$ be a solution of the
system~(\ref{eq:ii}).
Then the numerical series $\bar s_1$ converges iff the algebraic system
\begin{equation}
{x}_{i}=\bar r_{i}[{x}_{1},\ldots,{x}_{n}],\ i=1,\ldots,n\label{eq:iv}
\end{equation}
has a positive real solution.
\end{lem}
\begin{pf}
Assume that the series  $\bar s_{1}$ converges. We claim that in this
case for all $i$ the series $\bar s_i$ converges. In fact, this claim
was proved in the proof of Theorem~\ref{theor2}, part~II.
Let $s^{+}_i$ be the sum of the series $\bar s_{i}$. Then
$(s^{+}_1\ldots s^{+}_n)$ is the positive solution of the
system~(\ref{eq:ii}) (and hence~\ref{eq:iv}), because the rules of
addition and multiplication of FPS are well-defined for converging
series.

Conversely, let $\bar s_1$ diverge. Let us prove that the
system~(\ref{eq:iv}) has no positive solution. Assume the contrary:
$(a_1\ldots a_n)$ is a positive solution of the system~(\ref{eq:iv}),
that is, $a_i=\bar r_i[a_1,\ldots,a_n]$, $i=1,\ldots,n$.
Let $p^\alpha_i$ be the power series defined in the proof of
Theorem~\ref{theor0}. Let $\bar p^\alpha_i$ be the result of
substituting $c_1,\ldots,c_m$ for $t_1,\ldots,t_m$ in $p^\alpha_i$.
Clearly, $\bar p^\alpha_i$ are polynomials in $x_1,\ldots,x_n$
satisfying the equalities $\bar p^0_i=x_i$,
$\bar p^{\alpha+1}_i=\bar r_i[\bar p^\alpha_1,\ldots,\bar p^\alpha_n]$.
Therefore $a_i=\bar p^\alpha_i[a_1,\ldots,a_n]$ for all
$\alpha\in\Nset$ and all $i$ (this can be proved by  induction).
Consequently for all $\alpha $ we have
$a_1=\bar p^\alpha_1[a_1,\ldots,a_n]\ge
       \bar p^\alpha_1[0,\ldots,0]=\bar s^\alpha_1$
(where $s^\alpha_i$ were defined in the proof of Theorem~\ref{theor0}).
We claim that $\lim\limits_{\alpha\to\infty} \bar s^\alpha_1=+\infty$.
Indeed, for each $w\in\{t_1,\ldots,t_m\}^{*}$
\[
\lim_{\alpha\to\infty}(s^\alpha_1,w)=(s_1,w)
\]
and the numerical series  $\bar s_1$ diverges, hence
$\lim\limits_{\alpha\to\infty}\bar s^\alpha_1=+\infty$. Thus we
have got a contradiction: $a_1\ge +\infty $.

Lemma~\ref{lem2} is proved.
\end{pf}

Now, following \cite{sem}, in order to construct an algorithm deciding,
whether the domain of convergence of grammar's FPS is open,
we use the fact that the elementary theory of real field is decidable.
Due to Lemma~\ref{lem2} for each grammar we can construct a formula
$\varphi(c_1\ldots c_m)$ of this theory such that the FPS of the
grammar converges in a point $(c_1\ldots c_m)$ iff
$\varphi(c_1\ldots c_m)$ is true. Using $\varphi(c_1\ldots c_m)$, we
can construct a formula $\psi$ that is true iff the domain of
convergence of FPS is open.

Theorem~\ref{theor3} is proved.
\end{pf}

\section{Noninvariance}

A property ${P}$ of an unambiguous grammar is called {\em invariant\/}
if for any language generated by an unambiguous grammar satisfying $P$
any grammar that generates this language also satisfies $P$.
In connection with above results the following question arises:
are the properties of unambiguous grammar ``to be  weak
linear'' and ``to be strong nonlinear'' invariant?  The  answer
is unfortunately negative. The language of all nonempty words in a
binary alphabet (obviously having weak linear structure) can be
generated by some unambiguous grammar, which isn't weak linear.

\begin{thm}\label{theor4}
Consider the grammar $\{F\longrightarrow S$, $F\longrightarrow T$,
$F\longrightarrow TF$, $S\longrightarrow f$, $S\longrightarrow fS$,
$S\longrightarrow fT$, $S\longrightarrow fTS$, $T\longrightarrow l$,
$T\longrightarrow fTT\}$, where $F,S,T$ are
nonterminals, $F$ is the initial nonterminal, $f,l$  are  terminals.
This grammar is unambiguous, is not weak linear, and generates the
language of all nonempty words over the alphabet $\{f,l\}$.
\end{thm}

REMARK. For brevity the  grammar  has  rules  of  the  form
nonterminal$\,\longrightarrow\,$nonterminal. However the canonical
transformation of the grammar to the reduced form preserves all
properties listed in the theorem.

\begin{pf}
Obviously, the grammar isn't weak linear.

Let us explain the sense of the grammar.  The  nonterminals
mean: ${F}$ --- ``forest'', ${T}$ --- ``tree'', ${S}$ --- ``shoot'';
terminals  mean: ${f}$ --- ``fork'', ${l}$ --- ``leaf''.

\begin{defn}
A word $w$ over the alphabet $\{f,l\}$ is called
{\em a tree (a shoot)\/} if $w$ can by derived from the nonterminal $T$
(correspondingly $S$).
\end{defn}

The geometrical image of the tree ${l}$ is a single point. If ${u}$
and ${v}$ are trees, then the geometrical image of the tree $fuv$
consists of the root and the geometrical images of ${u}$ and ${v}$
growing from its two sons.

Let us describe the analysis of any word according to our grammar.
We try to find a beginning $u$ of the word such that $u$ is a tree.
If we are successful, then we erase $u$ and try again to find a
beginning that is a tree. And so on until the remaining word becomes
the empty word or a shoot.

The unambiguousness of the grammar follows from two lemmas.

\begin{lem}\label{lem3}
If a tree is a prefix of  another  tree  (in  this case we say that the
trees are consistent), then these trees are equal.
\end{lem}
\begin{pf}
By induction on the sum trees' lengths.
Let ${u}$ and ${v}$ be consistent trees. If one of them has length~1,
then the assertion is evident. Else $u=fu_1u_2$ and $v=fv_1v_2$, where
$u_1$, $u_2$, $v_1$, and $v_2$ are trees. We see that $v_1$ and $u_1$
are consistent. By induction hypothesis $u_1=v_1$. Therefore $u_2$ and
$v_2$ are consistent. By induction hypothesis $u_2=v_2$. Hence $u=v$.
Lemma~\ref{lem3} is proved.
\end{pf}

\begin{lem}\label{lem4}
No tree is a prefix (even improper) of a shoot.
\end{lem}
\begin{pf}
By induction on shoot's length. Suppose $w=uv$, where $w$ is a shoot
and $u$ is a tree. Then the word $u$ has the prefix $f$. Consider two
cases.

Case 1: $w=f$. Obviously we get a contradiction.

Case 2: $w=fz$, $z$ is nonempty. As $fz=uv$, the tree $u$ has the
form $fxy$, where $x$ and $y$ are trees. Therefore $z=xyv$.

As $fz$ is a shoot, three cases are possible: $z$ is a shoot, $z$
is a tree and $z$ is the concatenation of a tree and a shoot.

The case ``$z$ is a shoot'' contradicts the induction hypothesis.

If $z$ is a tree, then $z=x$ by Lemma~\ref{lem3} and
therefore the tree $y$ is empty; this is impossible.

If $z=z_tz_s$, where $z_t$ is a tree and $z_s$ is a shoot, then
$z_tz_s=xyv$. Therefore $z_t=x$ by Lemma~\ref{lem3}. Thus $z_s=yv$; this
contradicts the induction hypothesis.

Lemma~\ref{lem4} is proved.
\end{pf}

The following lemma shows that each word can be derived from the
initial nonterminal.

\begin{lem}\label{lem5}
If no prefix of a nonempty word is a tree, then this word is a shoot.
\end{lem}
\begin{pf}
By induction on the length of the given nonempty word $u$.

If the first letter of $u$ is $l$, then $u$ begins with a tree.

If $u=f$, then $u$ is a shoot.

If $u=fv$, where $v$ is nonempty and has no tree prefix, then by the
induction hypothesis $v$ is a shoot; therefore $u$ is also a shoot.

Let $u=fvw$ and $v$ be a tree. If $w$ is a shoot, then $u$ is also
a shoot. If $w$ is empty, then $u$ is again a shoot. Else  by the
induction hypothesis $w$ has a tree prefix (say) $z$; therefore $u$ has
a tree prefix $fvz$.

Lemma~\ref{lem5} is proved.
\end{pf}

As to the unambiguousness of this grammar, we can use
Lemmas~\ref{lem3},~\ref{lem4},~\ref{lem5} to prove by induction on
length of a word $u$ that from each nonterminal the word $u$ has not
more than one derivation tree.

Theorem~\ref{theor4} is proved.
\end{pf}

Let us prove that the property of an unambiguous grammar ``to be strong
nonlinear'' is also noninvariant. We shall say that any word over
$\{f,l\}$ derived from the nonterminal $T$ in the grammar of
Theorem~\ref{theor4} is a {\em tree}.
Evidently, the language of all trees is a language with strong
nonlinear structure.

\begin{thm}\label{theor5}
Consider  the  grammar
$\{T_0\longrightarrow l$, $T_0\longrightarrow fT_0T_0$,
$T_1\longrightarrow l$, $T_1\longrightarrow flT_1$,
$T_1\longrightarrow ffT_0T_0T_0\}$,
where $T_0$, $T_1$ are  nonterminals, $T_1$ is the initial nonterminal,
$f$, $l$ are terminals. This grammar is unambiguous, isn't strong
nonlinear, and generates the set of all trees.
\end{thm}
\begin{pf}
Obviously, the nonterminal $T_1$ isn't nonlinear and the nonterminal
$T_0$ is nonlinear. The sequence
$T_1,T_1,T_1,\ldots$ is the infinite quasiderivation, which does not
contain the nonlinear terminal $(T_0)$. Therefore this grammar isn't
strong nonlinear. Obviously, the words derived from $T_0$ are exactly
the trees. We can also prove by induction that only trees can be
derived from $T_1$.

Let us prove that every tree has a unique derivation from $T_1$ by
induction (the parameter of induction is the length of the tree $u$).

Evidently, if $u=l$, then $u$ has a unique derivation. Else
$u=fu_1u_2$, where $u_1$ and $u_2$ are trees.

If $u_1=l$, then any derivation of $u$ must begin with the rule
$T_1\longrightarrow flT_1$. By the induction hypothesis $u_2$ has a
unique derivation from $T_1$.

If $u_1\neq l$, then $u_1=fv_1v_2$, where $v_1$ and $v_2$ are trees.
In this case any derivation of ${u}$ must begin with the rule
$T_1\longrightarrow ffT_0T_0T_0$. By Theorem~\ref{theor4} every tree
has a unique derivation from $T_0$.

Theorem~\ref{theor5} is proved.
\end{pf}

\section{Conclusion}

The results of \cite{sem} and our Theorem~\ref{theor3} show that the
family of unambiguous grammars has some ``good'' algorithmic
properties, which the family of all context-free grammars doesn't have.
But significance of this fact is partially reduced because the property
of a grammar ``to be unambiguous'' is undecidable. Nevertheless the
state of affairs might be considered good if there would be a
recursively enumerable family of unambiguous grammars such that its
members generate all unambiguous languages. The following theorem
proved by K.~Yu.~Gorbunov shows that this is not the case.

\begin{thm}[see \cite{gor,gor1}]
There is no recursively enumerable set of context-free grammars (not
necessary unambiguous) such that the grammars of this set generate
exactly all unambiguous languages.
\end{thm}

The question whether such a family does exist is an example
of a problem of a certain type which, seems to be interesting. Let
we have an enumeration of some family of objects and we have a set $M$
of numbers with ``good'' algorithmic properties. Is there a recursively
enumerable subset of $M$ such that each object that has a number in $M$
has also a number in this subset?

The author thinks that the problem ``to enumerate a subset of $M$ such
that each object that has a number in $M$ has also a number in this
subset'' is more actual than the traditional problem of decision of $M$.

\begin{ack}
Author is grateful to N.~K.~Vereshchagin for help in writing
the draft version of the present paper.
\end{ack}


\newpage
\begin{thebibliography}{99}

\bibitem{gor}
Gorbunov, K.Yu. (1988):  ``On  one  algorithmic  problem  in
mathematical  linguistics'',  Proceedings  of  Symposium  on
Semiotical  aspects  of   formalization   of   intellectual
activity held  in  Borzhomi  (Georgia),  Moscow,  8--11  (in Russian).

\bibitem{gor1} Gorbunov, K. Yu. (1991): ``There is no recursively 
enumerable set of context free grammars generating the class of 
unambiguous languages'', Matematicheskie zametki, 50, N~1, 34--40 (in Russian).

\bibitem{much}
Muchnik, An.A. (1985): ``An application of Semenov's  method
to analysis of structure of  context-free  languages''.
Proceedings  of  Symposium   on   Semiotical   aspects   of
formalization  of  intellectual   activity   held   in   Kutaisi
(Georgia), Moscow, 212--214 (in Russian).

\bibitem{much1}
Muchnik, An.A. (1991): ``One application of real-valued interpretation
of grammatical series'', Preprint, Institute of New Technologies,
Moscow (in Russian).

\bibitem{sal}
Salomaa, A., Soittola, M. (1978):  ``Automata-theoretic
aspects of formal power series'', Springer Verlag.

\bibitem{sem}
Semenov, A.L.  (1973):  ``Algorithmic  problems  for  power
series and context-free grammars'',  Doklady  Akademii  Nauk
SSSR, {\bf 212}, 50--52 (in Russian).

\end{thebibliography}
\end{document}
