\documentclass[12pt]{article}
\usepackage{amssymb}
\sloppy

\begin{document}

\date{}
\title{One application of real-valued interpretation
of formal power series.}

\author{An.A. Muchnik\\
Institute of New Technologies,\\
Moscow,109004, Russia, Nizhnaya Radishevskaya 10,\\
fax 7095 915-69-63
}

\maketitle

\section*{Abstract}

{\it We define two natural properties of context free  grammars.
The first property generalizes linearity and the second property
strengthens nonlinearity. We call  languages  generated  by  the
unambiguous grammars of the first type the languages  with  weak
linear  structure  and  we  call  languages  generated  by   the
unambiguous grammars of  the  second  type  the  languages  with
strong nonlinear structure. Our main  theorem  states  that  the
family of unambiguous grammars  generating  the  languages  with
weak linear structure and the  family  of  unambiguous  grammars
generating the languages with  strong  nonlinear  structure  are
effectively separable.}

\section{Introduction}

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

We have called the grammars from first family  weak  linear
because this family  properly  includes  the  family  of  linear
grammars, and the grammars from second family  strong  nonlinear
because this family  is  properly  included  in  the  family  of
nonlinear grammars. Roughly speaking a grammar  is  called  weak
linear if we can  associate  with  each  nonterminal  a  natural
number called its rank in such a way 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 not  two  occurrences  of
nonterminals with rank equal  to  ${\rm rank}({x})$.  Roughly  speaking  a
grammar is called strong nonlinear if there are  arbitrary  long
derivations and if every sufficiently long  derivation  includes
as left hand side of rule some nonterminal ${x}$ such that from ${x}$ we
can derive a word having at least two occurrences of ${x}$.

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 demand 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 let us  restrict  ourselves  with  unambiguous
grammars. In some sense unambiguous grammar provide a  structure
to the generated language (for example,  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~3 states that we
can effectively separate  the  family  of  unambiguous  grammars
generating languages  having  weak  linear  structure  from  the
family  of  unambiguous  grammars  generating  languages  having
strong nonlinear structure. This is proved by an application  of
Semenov's method \cite{sem} consisting of the substituting in the power
series of a grammar reals for terminals. Theorem~2 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~4 and~5).

We begin with preliminaries consisting of some  well  known
facts from the theory of formal  power  series.  The  proofs  of
these facts (presented in that section) are  used  in  following
sections.

\noindent Author is grateful to N.K.Vereshchagin for help in writing
the draft version of the present paper.

\section{Preliminaries}

Context-free grammar may be defined by:

\noindent 1) two disjoint finite alphabets ${V}_{N}$, ${V}_{T}$,

\noindent 2) a finite set of rewriting rules,

\noindent 3) an initial symbol in ${V}_{N}$.

Symbols from ${V}_{N}$ will be called  {\it nonterminals},  and  symbols
from ${V}_{T}$ will be called {\it terminals.}

Each  rewriting  rule  has  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}$ {\it can be derived in  one  step  from  a
word ${w}_{1}$ by rewriting rule\/} ${x}\longrightarrow {u}$ if ${w}_{1}$ and ${w}_{2}$ can be  written  as
follows: ${w}_{1}={v}_{1}{xv}_{2}$, ${w}_{2}={v}_{1}{uv}_{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 {\it derivation of word ${w}$
from 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  initial   nonterminal)   will   be   called   simply
{\it derivation.}

The grammar {\it 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 {\it the language generated by the grammar.}

The grammar is called {\it reduced\/} if:

\noindent 1. Each nonterminal is a subword of some generated word.

\noindent 2. For each nonterminal there is some word over ${V}_{T}$ derived  from
it.

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

\noindent 4. The right hand side of any rewriting rule is not empty.

The property of a grammar  ``to  be  reduced''  is  obviously
decidable. Given a grammar we can construct a  reduced  grammar,
which  generates  the  same  language  except  the  empty  word.
(Reduced grammar  does  not  generate  the  empty  word  due  to
condition~4.)

If  it  is  not  stated  otherwise  we  will   assume   all
context-free grammars to be reduced.

For each grammar let  us  consider  the  set of  {\it 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.  We'll  define  by
induction the notion of a {\it derivation tree from a nonterminal}.

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

INDUCTION STEP. If ${T}$  is  a  derivation   tree   from   a
nonterminal ${y}$ and ${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 ${T}$ by adding ${n}$ edges with beginning ${l}$ and with ends
marked by ${a}_{1},\ldots,{a}_{n}$ from left to right is derivation  tree  from
${y}$.

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

LEMMA 0. {\it For  any  reduced  grammar,  the  size   of   any
derivation tree of a word ${w}$ is not more than $2\cdot {\rm length}(w)-1$.}

PROOF.  By  induction.  If  the  assertion  holds  for  all
subtrees with the  roots  in  the  sons  of  the  root  of  some
derivation tree then we can easily prove the bound for  the  whole
tree.

To formulate the first theorem we  need  the  notion  of  a
formal power series. A formal  power  series  (FPS),  or  simply
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 {\Bbb R}}$. We shall
call ${(a,w)}$  the
{\it coefficient of a on\/} $w$. We will consider 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 equation ${uv=w}$ means
that the concatenation of the words $u$ and $v$ is equal to $w$).
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
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  empty
word. The sum and the product of such  series  have  again  zero
constant terms.

Following \cite{sem} let us consider for  each  grammar  following
FPS of variables which are the terminals of  the  grammar.  This
FPS is $\sum\limits^{}_{{w}}{w\cdot }({a},{w})$, where $({a},{w})$ is equal to the number of different
derivation trees of  word ${w}$ (this  number  is  finite  due  to
Lemma~0). If the grammar  does  not  generate  a  word ${w}$,  then
$({a},{w})=0$. As the grammar is reduced, its FPS  has  zero  constant
term. We shall call  this  FPS  the  {\it 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 is one component  of
solution of some algebraic system of equations the  unknowns  of
which range the set of FPS. Let  us  substitute  positive  reals
from the domain of convergence of the FPS of the grammar for the
terminals. Then the sum of obtained numerical  series  satisfies
the numerical system of equations which  is  obtained  from  the
previous system by the same substitution.

Let us state well  known  theorem  (\cite{sal}),  formalizing  the
former assertion. We will also prove it because the  proof  will
be used in the sequel.

Let ${r}$ be 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}$. As ${s}_{1},\ldots,{s}_{n}$ have no constant term (remember
that we consider only FPS without constant  term)  we  can  easy
verify that we'll get a new power series. Let us  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
$$
x_{i}=r_{i},\ i=1,2,\ldots,n\eqno ({\rm i})
$$
as the system of equations in unknowns ${x_{1},\ldots,x_{n}}$. We'll  call  a
{\it solution\/} of (i)  any  tuple ${\langle s_{1},\ldots,s_{n}\rangle}$  of  FPS  of  variables
${t_{1},\ldots,t_{m}}$ such that ${s_{i}=r_{i}[s_{1},\ldots,s_{n}]}$ for all ${i=1,\ldots,n}$. The main
example of such a system is the following system. Suppose we are
given  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}$)
be all the rules with the  left  hand  side ${x}_{i}$.  Evidently  the
system
$$
x_{i}=u^{i}_{1}+\ldots+u^{i}_{k_{i}},\ i=1,\ldots,n\eqno ({\rm ii})
$$
has the form (i).
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
THEOREM 0. I. {\it Let for all $i$, $j$ no $r_{i}$ has terms of the  form
$ax_{j}$, $a\neq 0$. Then the system {\rm (i)} has a unique solution.}

II. {\it If $\langle {s}_{1},\ldots,s_{n}\rangle$ is  the  solution  of  the  system  {\rm (ii)}}
(unique according to the part I) {\it then $(s_{i},w)$ ($i=1,\ldots,n$) is
equal to the number of derivation trees of ${w}$ from ${x}_{i}$} (for  each
${w\in \{t}_{1},\ldots,t_{m}\}^{*}$).

PROOF. 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  the
length less than $|w|$ (by $|w|$ we denote the length  of ${w}$).  Thus
for all ${w}$ we have

\smallskip
\noindent if ${s}_{i}({v})={u}_{i}({v})$ for all ${v}$ such that $|v|<|w|$ and for all $i$\\
then $({r}_{i}[{s}_{1},\ldots,{s}_{n}],{w})=({r}_{i}[{u}_{1},\ldots,{u}_{n}],{w})$ for all $i$ $\phantom{AAAAAAAAAAAAA}^{\smash{{\textstyle (1)}}}$

\smallskip
\noindent Now let us prove the part I of the theorem.

\noindent Firstly, let us prove the uniqueness of  the  solution  of  (i).
Assume that the power series ${s}_{1},\ldots,{s}_{n}$; ${u}_{1},\ldots,{u}_{n}$  of  variables
${t}_{1},\ldots,{t}_{m}$ satisfy (i), that is
$$
{s}_{i}={r}_{i}[{s}_{1},\ldots,{s}_{n}],\ i=1,\ldots,{n}\eqno (2)
$$
and
$$
{u}_{i}={r}_{i}[{u}_{1},\ldots,{u}_{n}],\ i=1,\ldots,{n}\eqno (3)
$$
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  (1)  combined  with  (2)  and   (3)   yields   that
$({s}_{i},{w})=({u}_{i},{w})$. Contradiction.

Secondly, let us prove the existence  of  solution  of  the
system (i). Let us define the sequence $\langle {s}^{\alpha }_{1},\ldots,{s}^{\alpha }_{n}\rangle,\ \alpha \in {\Bbb N}$ of
tuples of power series of variables ${t}_{1},\ldots,{t}_{m}$ by induction.

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})
$$
Indeed, this can be proved by induction (the  parameter  of
induction is $|w|$). If $w=\Lambda$  then for all $\alpha \in {\Bbb N}$ $({s}^{\alpha }_{i},{w})=0$ 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
(1) involves that $({s}^{\alpha}_{i},{w})=({s}^{\beta}_{i},{w})$ for all ${i}$.

Let us define $\langle {s}_{1},\ldots,{s}_{n}\rangle$ as 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  (i)  that  is ${s_{i}=r_{i}[s_{1},\ldots,s_{n}]}$, ${i=1,\ldots,n}$.  Let  us   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)
$$
Because of (1) we have
$$
(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.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Let us prove the part II. Denote by ${r}_{i}$  the  power  series
${u}^{i}_{1}+\ldots+{u}^{i}_{k_{i}}$. As the grammar is reduced the system (ii)  satisfies
the assumption 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   equalities ${p}^{0}_{i}={x}_{i}$,
${p}^{\alpha+1}_{i}={r}_{i}[{p}^{\alpha}_{1},\ldots,{p}^{\alpha}_{n}]$.
Using induction we can easily prove  that  for
each $w\in ({V}_{N}\bigcup {V}_{T})^{*}$, $({p}^{\alpha }_{i},{w})$ is equal to the number  of  derivation
trees of the word ${w}$ from the nonterminal ${x}_{i}$ having size not more
than $\alpha $. 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 =2\cdot |w|$. Due to Lemma~0 each derivation tree of ${w}$ from ${x}_{i}$  has
size $\le \alpha $. Then\\
$({s}_{i},{w})=({s}^{\alpha }_{i},{w})=({p}^{\alpha }_{i},{w})=($number of derivation trees of ${w}$ from ${x}_{i}$
having size $\le\alpha)=($number of derivation trees of $w$ from ${x}_{i})$.

As $\langle {s}_{1},\ldots,{s}_{n}\rangle$ is the solution of (ii) we have proved  part II.

Theorem 0 is proved.

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

Remember that a grammar is called {\it linear\/} if right hand side
of any rewriting rule  has  not  more  than  one  occurrence  of
nonterminal. Let us call a nonterminal ${x}$ {\it nonlinear\/} if some  word
which contains at least two occurrences of ${x}$ can be derived from
${x}$.

DEFINITION. A grammar is called {\it weak linear\/} if it  has  not
nonlinear nonterminals.

In order to define the notion of strong  nonlinear  grammar
let us call {\it quasiderivation\/} any finite sequence ${x}_{1},{x}_{2},\ldots,{x}_{n}$  of
nonterminals such that ${x}_{1}$ is 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}$.

DEFINITION. A grammar is {\it strong nonlinear\/} if  1)~there  are
arbitrary long quasiderivations and 2)~every  sufficiently  long
quasiderivation has a nonlinear nonterminal.

Let us call {\it infinite quasiderivation\/} 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 would 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.

THEOREM 1. {\it Both properties of a grammar --- to be weak linear
and to be strong nonlinear --- are decidable.}

PROOF. 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 let us estimate for a nonlinear nonterminal ${x}$  the  minimal
size of derivation tree from ${x}$  having  (at  least)  two  leaves
marked by ${x}$. Number of sons of each vertex is bounded by maximal
length of 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 number of nonterminals multiplied by three.  Let  us  divide
this branch in 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 the size of new tree is less than the  size
of old one.

Let us prove the decidability of the  second  property.  To
this end we'll prove that both items of 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 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 1 is proved.

\noindent 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 important  tool  for  our  further
studies. In its formulation  the  terminals  are  considered  to
range the set of positive real numbers.

THEOREM 2. I. {\it The domain of convergence of FPS of any  weak
linear grammar is open.}

II. {\it The domain  of  divergence  of  FPS  of  any
strong nonlinear grammar is open.}

PROOF. I. Let us be given a weak linear grammar.

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

Let us define rank of nonterminals.  To  this  end  let  us
define for each ${r\in {\Bbb N}}$ 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}$. Define the {\it rank\/} of a nonterminal ${x}$ to  be  the  least ${r}$
such that ${x\in A}_{r}$.

We can easily verify the following properties of 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 with rank more than ${r}$.

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

A weak linear grammar has the third property.

3) If the left hand side of some rewriting rule consists of
a nonterminal of rank ${r}$ then its right hand side cannot have the
form ${uy}_{1}{vy}_{2}{w}$ where ${y}_{1}$ and ${y}_{2}$ are (possibly  equal)  nonterminals
of rank ${r}$.

We could  define  weak  linear  grammar  to  be  a  grammar
satisfying the third  property.  The  new  definition  would  be
equivalent to the definition given in section~3.

We have to prove that the domain of  convergence  of  power
series of the grammar is open. To this end let us use  Theorem~0
according to which the power series of the grammar satisfies the
system~(ii).

In the case of linear grammar the system (ii)  consists  of
equations linearly depending on the nonterminals. In the case of
weak linear grammar the system (ii) can be  split  into  ``almost
linear'' systems. Namely, if we separately  consider  the  system
consisting of all equations with nonterminals of rank ${r}$  in  the
left hand side and consider the nonterminals of rank less than ${r}$
to be known then we get a linear system.

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

Let us call a power series  {\it good\/}  if  the  following  three
conditions are satisfied (remember that  we  consider  only  the
series with zero constant term and that the range  of  variables
is the set of positive reals):

0) all coefficients of the series are nonnegative;

1) the  domain  of  convergence  of  the  series   can   be
represented as set of  all  solutions  of  a  system  of  strict
rational  inequalities  (i.e.\ the  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);

2) within the domain of convergence the sum  of  series  is
a rational function of its variables.

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

LEMMA 1. {\it Let}
$$
\{x_{i}=b_{i}+\sum^{n}_{j=1}a_{ij}{x}_{j}\,\colon\ i=1,\ldots,n\}\eqno ({\rm iii})
$$
{\it be a system in unknown\/} FPS ${x}_{1},\ldots,{x}_{n}$ {\it and all ${b}_{i}$ and ${a}_{ij}$ be  good\/}
FPS. {\it Then this system has a unique  solution $\langle {s}_{1},\ldots,{s}_{n}\rangle$  where
all ${s}_{i}$ are good\/} FPS.

PROOF. From Theorem 0 it follows that the system (iii)  has
a unique solution. Moreover the  well  known  theorem  from  \cite{sal}
states that the solutions ${s}_{i}$ of system  (iii)  can  be  obtained
from its coefficients with finite number of applications of  the
operations of sum, product and the binary operation ${p,q}\longrightarrow {p}^{*}\cdot {q}$.
The operation ${s}^{*}$ (or star-operation) can be applied only to  FPS
with  zero  constant  term  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 S.C.Kleene on regularity of recognizable sets.

We have to 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  0)  for ${p}+{q}$,
${p\cdot q}$, ${p}^{*}\cdot {q}$ is evident. Let us verify that ${p}+{q}$, ${p\cdot q}$, ${p}^{*}\cdot {q}$  satisfy
1) and~2).

SUM. The domain of convergence of the sum of series ${p}+{q}$  is
equal to the intersection of the domains of convergence of ${p}$ and
${q}$ because due to~0) 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  the  sum  of
series ${p}$ and 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 1) and 2) 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 system defining the domain of convergence  of ${r}$  and
additional inequality ${\rm sum}({r})<1$.

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

Lemma 1 is proved.

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

Remember  the  described  procedure  of  solving  (ii)   by
sequential solving of subsystems of (ii) corresponding to values
of rank of left hand side. Let us prove by  induction  that  all
subsystems solved in this process  satisfy  the  assumptions  of
Lemma~1. Every subsystem can be reduced to  the  form  (iii)  by
permutation  of  multipliers  in  terms.  And  the  coefficients
${b}_{i}$, ${a}_{i,j}$ are obtained from terminals and  solutions  of  previous
subsystems by  additions  and  multiplications.  Note  that  the
solutions of new system as functions from ${\Bbb R}^{m}$ into ${\Bbb R}$ are equal to
the solutions of old system.

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

II. Let us be given a strong nonlinear grammar.

Consider the system (ii) associated with this grammar.  Let
$\langle {s}_{1},\ldots,{s}_{n}\rangle$ be the solution of (ii). Remember 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  we  denote  by
${s}_{i}({c}_{1},\ldots,{c}_{m})$ the result of substitution ${c}_{1},\ldots,{c}_{m}$ for ${t}_{1},\ldots,{t}_{m}$
in ${s}_{i}$ (${s}_{i}({c}_{1},\ldots,{c}_{m})$ is the numerical series).

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

The following assertions will be useful.

1) There is  a  nonlinear  nonterminal ${x}_{i}$  such  that  the
numerical series ${s}_{i}({c}_{1},\ldots,{c}_{m})$ diverges.

2) For  every  nonlinear  nonterminal ${x}_{i}$  the  domain   of
divergence of the series ${s}_{i}$ is open.

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 {\Bbb N}$
such that some term of ${p}^{\alpha }_{1}$ has an occurrence  of ${x}_{i}$ (the  power
series ${p}^{\beta }_{j}$, $\beta \in {\Bbb N}$, $j=1,\ldots,{n}$ were defined in the proof of part II
of Theorem~0 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 $j$-th  equation  in
(ii)). Using induction we can easy prove that for all $\beta \in {\Bbb N}$  it
holds ${s}_{j}={p}^{\beta }_{j}[{s}_{1},\ldots,{s}_{n}]$ for all $j=1,\ldots,n$.

Hence ${s}_{1}={p}^{\alpha }_{1}[{s}_{1}\ldots {s}_{n}]$. The condition~2) in the definition of
reduced grammar and Theorem 0(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}$ has  an
occurrence in 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 which $s_{i}$ diverges in.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Thus it remains to prove 1) and 2).

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   strong
nonlinearity  it  is  sufficient  to   construct   an   infinite
quasiderivation in which every nonterminal has divergent  series
in the point $({c}_{1},\ldots,{c}_{m})$. This quasiderivation begins  with  the
initial    nonterminal ${x}_{1}$.    The    system    (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 will 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
nonlinearity there is $\alpha $ such that  the  series ${p}^{\alpha }_{i}$  has  a  term
having  at  least  two   occurrences   of ${x}_{i}$.   As   mentioned
${s}_{i}={p}^{\alpha }_{i}[{s}_{1}\ldots {s}_{n}]$ (for  all $\alpha$).   After   some   permutation   of
multipliers we will 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
simple 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 2 is proved.

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

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

DEFINITION. We'll say  that  a  language  has  {\it weak  linear\/}
({\it strong nonlinear\/})  structure  if  it  can  be  generated  by  a
unambiguous  weak  linear  (correspondingly  strong   nonlinear)
grammar.

THEOREM 3. {\it The  family   of   all   unambiguous   grammars
generating languages which have weak linear  structure  and  the
family of all  unambiguous  grammars  generating  the  languages
which  have  strong  nonlinear  structure  are   algorithmically
separable.}

PROOF. The  following  decidable  property  separates  two
families under consideration. A grammar  has  this  property  if  the
domain of convergence of its FPS is open. We have to prove  that
this property separates the families and is decidable.

Let ${G}_{1}$ be an unambiguous grammar generating  a  language ${L}$
which has 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~2  the  domain  of  convergence  of  this
series is open, q.e.d.

Let ${G}_{1}$ be an unambiguous grammar generating  a  language ${L}$
which has 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 the 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, unambiguous series has not more than ${m}^{l}$
terms  with  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  has  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  (ii)  for  this  grammar.  Let
${c}_{1},\ldots,{c}_{m}$ be positive reals. Let ${r}_{i}$ stands for  the  right  hand
side of $i$-th equation in (ii), that is ${r}_{i}={u}^{i}_{1}+\ldots+{u}^{i}_{k_{i}}$. As ${r}_{i}$  has
finite number of terms  after  the  substitution ${c}_{1},\ldots,{c}_{m}$  for
${t}_{1},\ldots,{t}_{m}$ we'll get a power series with finite number  of  terms
of  variables ${x}_{1},\ldots,{x}_{n}$.  Let  us   denote   this   series   by
${\bar r}_{i}[{x}_{1},\ldots,{x}_{n}]$. We will regard this series  as  a  polynomial  of
(commuting) variables ${x}_{1},\ldots,{x}_{n}$. Let us denote  also  for  every
power  series ${s}$  of   variables ${t}_{1},\ldots,{t}_{m}$   with   nonnegative
coefficients by ${\bar s}$  the numerical series obtained by  substitution
${c}_{1},\ldots,{c}_{m}$ for ${t}_{1},\ldots,{t}_{m}$ in ${s}$ (the nonnegativeness of coefficients
ensures that its convergence doesn't  depend  on  the  order  of
terms).

LEMMA 2. {\it Let $\langle {s}_{1},\ldots,{s}_{n}\rangle$ be the solution  of  system  {\rm (ii)}.
Then the numerical series ${\bar s}_{1}$ converges iff the algebraic system}
$$
{x}_{i}=\bar r_{i}[{x}_{1},\ldots,{x}_{n}],\ i=1,\ldots,n\eqno ({\rm iv})
$$
{\it has positive real solution.}

PROOF. Assume that the series  $\bar s_{1}$ converges. We  claim  that
in this case for all $i$ the series  $\bar s_{i}$ converges.  This  claim  in
fact was proved in the proof of part II of Theorem~2. Let ${s}^{+}_{i}$  be
the sum of  the  series   $\bar s_{i}$.  Then $({s}^{+}_{1}\ldots {s}^{+}_{n})$  is  the  positive
solution of system (ii) (and hence  iv)  because  the  rules  of
addition and multiplication of FPS are correct.

Conversely, let  $\bar s_{1}$ diverge. Let us prove  that  system  (iv)
has no positive solution. Assume the contrary: $({a}_{1}\ldots {a}_{n})$  is  a
positive solution  of  system  (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~0. Define $\bar p^{\alpha }_{i}$ to be the result of substitution ${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 {\Bbb N}$ and all $i$ (proved by  induction).
Consequently for all $\alpha $ we have ${a}_{1}=\bar p^{\alpha}_{1}[{a}_{1},\ldots,
{a}_{n}]\ge\ldots\ge\bar p^{\alpha}_{1}[0,\ldots,0]=\bar s^{\alpha}_{1}$
(${s}^{\alpha}_{i}$ was defined in the proof of Theorem~0).  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 2 is proved.

Now, following \cite{sem}, let us make use of the decidability  of
the elementary theory of ordered field  of  reals  in  order  to
construct an algorithm deciding whether domain of convergence of
FPS of a grammar is open. Due to Lemma~2 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 $  which  is
true iff the domain of convergence of FPS is open.

Theorem 3 is proved.

\section{Noninvariance}

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 property ${P}$
of unambiguous grammar is called invariant if every  unambiguous
grammar generating a language  which  can  be  generated  by  an
unambiguous grammar satisfying ${P}$ itself satisfies ${P}$. The  answer
is unfortunately negative. The language of all nonempty words in
binary alphabet obviously having weak linear  structure  can  be
generated by an unambiguous grammar which isn't weak linear.

THEOREM 4. {\it 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\}$.}

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 theorem.

PROOF. 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''.

DEFINITION. Let us call a tree (a shoot) any word over  the
alphabet $\{f,l\}$  which  can  by  derived  from   nonterminal ${T}$
(correspondingly ${S}$).

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 the beginning of the  word  which  is  a
tree. If we are successful then we erase this beginning and  try
again to find the beginning of the word which is a tree. And  so
on until the remaining word becomes empty or is a shoot.

The unambiguousness of the grammar follows from two lemmas.

LEMMA 3. {\it If a tree is a prefix of  another  tree  (in  this
case we say that the trees are consistent) then these trees  are
equal.}

PROOF. By induction. (The parameter of induction is the sum
of lengths of trees.) Let ${u}$ and ${v}$ be consistent trees. If one of
them has length~1 then the assertion is evident.  Else ${u}={fu}_{1}{u}_{2}$,
and ${v}={fv}_{1}{v}_{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~3 is proved.

LEMMA 4. {\it No tree is a prefix (even improper) of a shoot.}

PROOF. By induction (the  parameter  of  induction  is  the
length of the shoot). Suppose ${w}={uv}$, where ${w}$ is a shoot and ${u}$  is
a tree. Then the word ${u}$ has 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 concatenation of a tree and a shoot.

If ${z}$ is  a  shoot  then  we  have  the  contradiction  with
induction hypothesis.

If ${z}$ is a tree then ${z}={x}$ by Lemma~3 and therefore the tree ${y}$
is empty which is impossible.

If ${z}={z}_{t}{z}_{s}$ where ${z}_{t}$ is  a  tree  and ${z}_{s}$  is  a  shoot  then
${z}_{t}{z}_{s}=xyv$ therefore ${z}_{t}={x}$ by Lemma~3. Thus ${z}_{s}={yv}$ which contradicts
the induction hypothesis.

Lemma 4 is proved.

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

LEMMA 5. {\it If nonempty word has no prefix  which  is  a  tree
then this word is a shoot.}

PROOF. By induction (the  parameter  of  induction  is  the
length of 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
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
induction hypothesis ${w}$ has a tree prefix (say) ${z}$ therefore ${u}$ has
a tree prefix $fvz$.

Lemma 5 is proved.

As to unambiguousness of this grammar we can use the lemmas
3,4,5 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 4 is proved.

Let us prove that the property of unambiguous  grammar  ``to
be strong nonlinear'' is also noninvariant. We'll call {\it trees\/}  all
words over $\{f,l\}$ derived from the nonterminal ${T}$ in  the  grammar
of Theorem~4. Evidently the language of  all  trees  has  strong
nonlinear structure.

THEOREM 5. {\it Consider  the  grammar $\{T_{0}\longrightarrow l$, $T_{0}\longrightarrow fT_{0}{T}_{0}$,
${T}_{1}\longrightarrow {l}$, ${T}_{1}\longrightarrow flT_{1}$, ${T}_{1}\longrightarrow ffT_{0}{T}_{0}{T}_{0}\}$ where $T_{0}$, $T_{1}$ are  nonterminals,
${T}_{1}$ is initial nonterminal, $f$, $l$ are terminals.  This  grammar  is
unambiguous, isn't strong nonlinear and generates the set of all
trees.}

PROOF. Evidently, the nonterminal ${T}_{1}$ isn't  nonlinear.  The
sequence ${T}_{1},{T}_{1},{T}_{1},\ldots$  is  infinite  quasiderivation  having  no
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}$).

If ${u}={l}$ then ${u}$ has evidently unique derivation. Else ${u}={fu}_{1}{u}_{2}$
where ${u}_{1}$ and ${u}_{2}$ are trees.

If ${u}_{1}={l}$ then the derivation of ${u}$ must begin with  the  rule
${T}_{1}\longrightarrow flT_{1}$. By induction hypothesis ${u}_{2}$ has unique derivation from
${T}_{1}$.

If ${u}_{1}\neq {l}$ then ${u}_{1}={fv}_{1}{v}_{2}$ where ${v}_{1}$ and ${v}_{2}$ are  trees.  In  this
case the derivation of ${u}$ must begin with the rule ${T}_{1}\longrightarrow ffT_{0}{T}_{0}{T}_{0}$.
By Theorem~4 every tree has unique derivation from ${T}_{0}$.

Theorem 5 is proved.

\section{Conclusion}

The results of \cite{sem} and our Theorem 3 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 is 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
a case.

THEOREM 6.(\cite{gor}). {\it There is no recursively enumerable  set  of
context-free grammars (not necessary unambiguous)  the  grammars
of which generate exactly all unambiguous languages.}

The question whether such a family does exist is an example
of a problem of certain type which seems to be interesting.  Let
we are given an enumeration of a family of objects  and  we  are
given a set ${M}$ of numbers with ``good'' algorithmic properties.  Is
there a recursively enumerable subset of ${M}$ such that each object
which 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 which has a number in ${M}$  has  also  a
number in this subset''  is  more  actual  than  the  traditional
problem of decision of ${M}$.

\newpage
\begin{thebibliography}{99}

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

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

\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{much1}
Muchnik, An.A. (1991): ``One application of real-valued interpretation
of grammatical series.'', Preprint, Institute of New Technologies,
Moscow (in Russian).

\end{thebibliography}
\end{document}

