数理解析研究所講究録
第 1744 巻 2011 年 144-150

144

2010 年度冬の LA シンポジウム [28]Cancel minimal linear grammars
with a particular nonterminal symbol
Kaoru Fujioka

Hirofumi Katsuno \dag er*

symbol except and examine the generative powers
of a cancel minimal linear grammar with a unique canAmong the variety of normal forms for phrase struc- cellation production
for any $m\geq 1$ . We
mre grammars ([1], [2], [4]), Geffert normal forms in show that for any given $m\geq 1$ , cancel minimal linear[1] are unique in that each of them consists of contextonly generate linear languages.
grammars withfree type productions with a fixed number of specific In contrast to this, forwith not bounded,
ofnonsequenceareplacecancellation productions thatthe class of languages generated by those grammars is
terminal symbols with the empty string .
shown to be equivalent to the class oflinear languages.
In [3], Geffert normal forms are formaIized into a
These results imply a new hierarchy oflanguage clasgrammar which has minimal linear type productions ses using cancel minimal linear grammars[3].
and a finite set of cancellation productions, called cancel minimal linear grammar. Within the framework ofcancel minimal linear grammars, one of the Geffert’s 2 Preliminaries
results ([1]) means that the cancel minimal linear gram-

1

Introduction

$S$

$C$

$C^{m}arrow\epsilon$$C^{m}arrow\epsilon$$C^{m}arrow\epsilon$$m$$\epsilon$

mar with two cancellation productions

and$CCarrow\epsilon$
generates any recursively enumerable lan$ABarrow\epsilon$

guage.
The generative powers of the cancel minimal linear
grammars are examined in [3] especially with only oneof the two cancellation productions above under the assumption of dealing with only -free languages. It has
been shown that any language generated by the cancel
is context-free,minimal linear grammar withand that any linear language can be generated by thegrammar. Furthermore, the class of languages generated by the cancel minimal linear grammar withis showed to be a proper subset ofthe class oflinear lan$\epsilon$$ABarrow\epsilon$$CCarrow\epsilon$

guages.
In this paper, we consider a particular nonterminal’Office for Strategic Research Planning, Kyushu University.

\dagger Department of Science and Engineering, Tokyo Denki University.

We assume the reader to be familiar with the mdiments in formal language theory from [4].
A phrase structure grammar (a grammor for short)
is a quadruple $G=(N, T,P,S)$ , where $N$ is a set of

nonterminal symbols, is a set of teminal symbols,
is a set of productions, and in is the initial symbol.
, whereA production in is of the form$(N\cup T)^{*}N(N\cup T)$ and $\pi_{2}\in(N\cup T)^{*}$ . For any
,
, if
in
and
. If
, then we writeand :. Similarly, for ais understood, we write.
sequence of productions , we simply write
Further, ifthere is no confusion, we simply write, and we denote the reflexive and transitive closure of
$P$

$T$

$S$

$P$

$N$

$\pi_{1}arrow\pi_{2}$$\pi_{1}\in$$\alpha_{1}$$\alpha_{2}$$r$$(N\cup T)^{*}$$\alpha_{1}=\alpha_{11}\pi_{1}\alpha_{12},$$\alpha_{2}=\alpha_{11}\pi_{2}\alpha_{12}$$\alpha_{1}=^{r}c\alpha_{2}$$\pi_{1}arrow\pi_{2}\in P$$\alpha_{1}\Rightarrow^{r}\alpha_{2}$$G$$\alpha_{1}\Rightarrow\gamma\alpha_{2}$$\gamma$$\alpha_{1}\Rightarrow$$\alpha_{2}$.
We define a language $L(G)$ generated by a grammar$G=(N, T,P,S)$ as follows: $L(G)=\{z\in T^{*}|S\Rightarrow^{*}z\}$ .
$\Rightarrow by\Rightarrow.$

145
It is well known that the class of languages generated mar is introduced as follows [3].
by the phrase structure grammars is equal to the class
Definition 1 A grammar $G=(\{S\}\cup N_{C}, T, P,S)$ is anofrecursively enumerable languages.
-cancel minimal linear grammar $(\Omega-cml$ grammarfor
A language is said to be -free, if it contains noempty string . In this paper, we deal with only -free short) ifit satisfies the following.
(1)is the initial symbol.
languages.
is afinite set of nonterminal symbols except .
A grammar $G=(N, T, P,S)$ is linear if each pro- (2)is afinite set ofterminal symbols.
duction in is of the form
, where $N_{i}\in N$ (3), where.
and contains at most one nonterminal symbol. A lan- (4)$P=P_{M}\cup
P_{C}$
is afinite set ofproductions, whereguage generated by any linear grammar is also called (5)$\Omega$$L$$\epsilon$$\epsilon$$\epsilon$

$S$

$S$

$N_{C}$$P$$T$$N_{i}arrow\alpha$$\Omega=\{\Omega_{i}|1\leq i\leq n\}$$\alpha$linear. It is obvious that any linear language can be generated by a linear grammar each ofwhose productions
is ofthe form
, or
, where$(a)$$\Omega_{i}\in N_{C}^{+}$$P_{M}\subseteq\{Sarrow\alpha_{1}S\alpha_{2},$$Sarrow\alpha|$,$\alpha_{1},\alpha_{2},\alpha\in(T\cup N_{C})^{*}\}$

$(b)$
.
We
a
production
call
in
a
minimallinear type
$N_{1},N_{2}\in N$ and $u\in\tau*$ .
production (an ml-production for short) and call a proA grammar $G=(N, T,P,S)$ is right (resp. left) linear
a cancellation production (a c-production
duction in
if it is linear and every production in is of the form
$N_{1}arrow uN_{2},$ $N_{1}arrow N_{2}u$$P_{C}=\{\Omega_{i}arrow\epsilon|1\leq i\leq n\}$$N_{1}arrow u$$P_{M}$$P_{C}$$P$$N_{1}arrow uN_{2}$or$N_{1}arrow u$

$($

resp.

$N_{1}arrow N_{2}u$or$N_{1}arrow u)$,

where $N_{1},N_{2}\in N$ and. Any language generated
by such a grammar is called right (resp. left) linear. It
is well known that the class of right linear languages is
equivalent to the one of left linear languages, which isalso called the class of regular languages.
A grammar $G=(N, T, P,S)$ is minimal linear if $N=$and every production in is of the form $Sarrow uSv$
$w\in T^{*}$
or $Sarrow w$ , where. Any language generated
by such a grammar is called minimal linear.
Let $RE,$ $LIN,$ $REG$ , and $ML$ be the classes of recursively enumerable, linear, regular, and minimal linear
languages, respectively.
Geffert [1] shows the following theorem for recursively enumerable languages.

for short).

A language$u\in T^{*}$$P$$\{S\}$$u,$ $v,$

Theorem 1 Any recursively enumerable language canbe generated by a grammar $G=(\{S\}\cup N_{C}, T,P\cup P_{C},S)$
satisfying the following conditions:
Every production in is of the $fomSarrow\alpha_{1}S\alpha_{2}$ or, where,$N_{C}=\{A,B, C\}$ and $P_{C}=\{ABarrow\epsilon, CCarrow\epsilon\}$.

.

$P$$Sarrow\alpha$$\alpha_{1},\alpha_{2},\alpha\in(T\cup N_{C})^{*}$

Motivated by th is Geffert normal form, a new gram-

guage (
grammaris an-cancel minimal linear lanlanguage for short) if there is ansuch that $L=L(G)$ .
$L$$\Omega$$\Omega-cml$$G$

For a string$\Omega-cml$$\alpha^{R}$$\alpha,$represents the reverse of .
$\alpha$Definition 2 Ifan ml-production has the right side withno terminal symbol, then the production is called aterminal-free ml-production, otherwise it is calleda terminal ml-production.
Angrammaris called a terminal
grammar if any ml-production in is one ofthe formsof a terminal production. A language is called aterminal
language if there is a terminal
grammar that generates .
$\Omega-cml$$\Omega-cml$

$G$

$P$

$L$

$\Omega-cml$$\Omega-cml$$L$

The classes ofterminal -cml languages are denoted.
by
The generative powers of some classes of terminal-cml grammars{AB}-cml grammars and terminala examined in [3] and the following theorem is theareresult conceming terminal-cml grammars.
$\Omega$$t-CML_{\Omega}$$\rceil$$\{C^{2}\}$

$|$

$1$

theorem 2$\{C^{2}\}$

146
According to the six forms above, we partition the set$P(6)$
into six sets $P(1),$ $P(2),$of ml-productions
are incomparable.
2. $REG$ andsuch that for each $n(1\leq n\leq 6),$ $P(n)$ consists of ml-cml gram- productions in the n-th form above. Let $P(t)$ be a set
In this paper, we focus on a terminalof terminal ml-production in and $P(tf)$ be a set of
mar for any positive integer .
terminal-free ml-production and the c-production, then

1. $ML\subset t-CML_{|c-|}\subset LIN$

$P_{M}$$\ldots,$$t-CML_{|C^{2}|}$$\{C^{m}|$

$P$

$m$

3

Terminal$\{C^{m}\}$$P(t)=$-cml languages$P(t!)=$$P(1)UP(2)\cup P(3)UP(4)$$P(5)\cup P(6)\cup\{r_{C}|$.

In this section, we consider the generative power ofIn the following, we call a production in $P(tf)$ as a-cml grammars. The case $m=1$ is simterminal$\{C^{m}\}$ple, becausemeans that can be canceled any
time in derivations. Therefore, the following lemma is
obvious.

terminal-free production.

$C$$Carrow\epsilon$-cml grammars andnondeterministic finite automatons

3.2 Terminal

Lemma 1 $t-CML_{|C|}=ML$ .

$\{C^{m}\}$-cml grammar
We show that for any terminal, there exists a nondeterministic finite automatonsuch that $L(M_{G})$ and $L(G)$ are closely related.
In the following, let $Sarrow C^{i}uC^{k}SC^{l}vC^{j}$ be an mlproduction in $P(1)\cup P(2)\cup P(3)$ with $v\in\tau*$ andthen $k=0$ , and. Then, we assume that if$\{C^{m}|$In the following, we consider the case $m\geq 2$ .

3.1

$G$

Minimal linear type productions$M_{G}$$u,$In the following, for simplicity, if $i=0$ then we
as in ml-productions ofregard ‘ andcml grammars. For example, the ml-production $Sarrow$$C^{j}uC^{m-i}S$
represents $Sarrow uS$ for $i=0$ .
-cml grammar $G=(\{S,C\}, T, P,S)$ , weIn every
may assume that any ml-production in is one of the$C^{m-i}$$C$$\{C^{m}\}-$$\epsilon$$\{C^{m}\}$$P$

six forms,(1)$Sarrow C^{j}uC^{k}SC^{l}vC^{j}$(3)$Sarrow C^{j}SC^{l}vC^{j}$(5)$Sarrow C^{i}SC^{j}$

,

,

(2)

$Sarrow C^{j}uC^{k}SC^{j}$(4)$Sarrow C^{i}uC^{j}$(6)$Sarrow C^{j}$

,

,

$u,$

$T^{*}$$u,$ $u\in T^{+}$$u,$ $v\in T^{+}$$T^{*}$

that if$v=\epsilon$

then $l=0$ .

Definition 3 For a terminal $\{C^{m}|-cml$ grammar $G=$$\{qoI)$ is a nonde$(\{S,C), T,P,S),$ $M_{G}=(Q,\Sigma_{G},\delta,$
terministic finite automaton derivedfrom , where$q_{0,0},$

$G$

$Q=$

$\{q_{i,j}|0\leq i,j<m\}\cup\{q_{0}\}$,$\Sigma_{G}=\{[u|v]|Sarrow C^{i}uC^{k}SC^{l}\iota^{R}C^{j}\in$$P(1)\cup P(2)\cup P(3))\cup$,

where $v\in T^{+},$ $0\leq i,j,k,$ $l<m$ . This is because
any ml-production can be transformed into one of the,:above forms by using the c-productionor the ml-production makes no contribution to produce
a string in . For example, an ml-production $Sarrow$$C^{m+i}uC^{k}SC^{2m+l}vC^{j}$and $0\leq i,j,k,1<m$ ,withis equivalent to $Sarrow C^{i}uC^{k}SC^{l}vC^{j}$ , whereas an mland $0<i<m$ isproduction $Sarrow uC^{l}vS$ withuseless to produce a string in .
$r_{C}$$u=\epsilon$$uv\neq\epsilon$$C^{m}arrow\epsilon$$\{[u]|Sarrow C^{i}uC^{j}\in P(4)\}$.

The transition mapping is defined as follows:is in $P(1)$ , then$\delta$$IfSarrow C^{i’}uC^{k}SC^{l}\mathfrak{s}_{j^{R}}c^{f}$$\delta(q_{i,j}, [u|v])\ni q_{k,l}$with $i=(m-i’)mod m$ $andj=(m-f)mod m$ .
$IfSarrow C^{i’}uC^{k}SC^{f}$ is in $P(2)$ , thenfor each $j(0\leq j<m),$with $i=(m-i’)mod m$ and $l=0+f$ ) $mod m$ .
$IfSarrow C^{i’}SC^{l_{j}R}C^{j’}$ is in $P(3)$ , thenfor each $i(0\leq i<m),$$\delta(q_{i,j}, [u|\epsilon])\ni q_{k,l}$$\delta(q_{i,j}, [\epsilon|v])\ni q_{k,l}$147
with $k=(i+i’)mod m$ $andj=(m-j’)mod m$.
$IfSarrow C^{j’}uC^{j’}$ is in $P(4)$ ,then$\delta(q_{i,j}, [u])=\{q_{0}\}$by using the induction on . Note that for the case $i=$$j=0$ , this implies Theorem 3.
. By
Base step, $n=0$ : Assume thatthe constmction of , there is a production : $Sarrow$with $i=(m-i’)mod m$ and $j=(m-j’)mod m$ .
Therefore,holds.
1, assume that
Induction step: For. Then,is an element of$n$$\delta(q_{i,j}, [u])\ni q_{0}$with $i=(m-i’)mod m$ $andj=(m-j’)mod m$ .
We extend by induction to a function :according to the rules;$\delta$$\delta^{*}$$Q\cross\Sigma_{G}^{+}arrow$$\mathcal{P}(Q)$$\delta$‘$C^{i}$$r$$uC^{j’}$$C^{i}SC^{j}\Rightarrow^{r}C^{i}C^{i’}uC^{j’}C^{j}\Rightarrow^{*}u$$n$$\delta^{*}(q,\sigma)=\delta(q, \sigma)$,$\geq$$q_{0}$$\delta(q_{i,j}, [u_{1}|v_{1}]\cdots[u_{n}|v_{n}][u])$such that
there is a stateand. From the inwhere aand.
duction hypothesis, there is a derivation, then we use theMoreover if.
notationto denote$v_{1};(1)u_{1},$There are three cases forfor simplicity.
. We prove only
We note the following points aboutin Defini- the first case, since the proof ofthe other cases is quitetion 3.
similar to the proof ofthe first case.
. By the constmction of ,Assume that
1. Intuitively, a state $q_{i,j}(0\leq i,j<m)$ in
corre:
insponds to a derivation
for some there is a production
with $i=(m-i’)mod m$ and $j=(m-f)mod m$ . The.
refore, there is a derivation
2. An ml-production in $P(1)\cup P(4)$ produces a uniquetransition, while an ml-production in $P(2)\cup P(3)$.
produces kinds oftransitions.
,$\delta^{*}(q,\alpha\sigma)=\bigcup_{q’\in\delta(q,\alpha)}\delta(q’,0^{\cdot})$$\delta(q_{i,j}, [u_{1}|v_{1}])$$q_{k,l}$$\ni$$q_{k,l}$$\delta(q_{k,l}, [u_{2}|v_{2}]\cdots[u_{n}|u_{n}][u])\ni q_{0}$$\in\Sigma_{G}$$\alpha\in\Sigma_{G}^{+}$$C^{k}SC^{l}\Rightarrow^{*}$$\alpha=[u_{1}|v_{1}^{R}]\cdots[u_{k}|\iota j^{R}k]$$u_{2}\cdots u_{n}u\iota_{n}^{R}\cdots f_{2}$$\delta^{*}(q, [u_{1}\cdots u_{k}|(v_{1}\cdots v_{k})^{R}])$$\delta^{*}(q,\alpha)$$u_{1}\neq\epsilon;(2)$$u_{1},$$u_{1}=\epsilon,$$u_{1}\neq\epsilon;(3)u_{1}\neq\epsilon,$$v_{1}=\epsilon$$M_{G}$$u_{1},$$\delta$$v_{1}\neq\epsilon$$M_{G}$$r$$Sarrow C^{\gamma}u_{1}C^{k}SC^{l}\iota_{1}^{R}C^{f}$$P$$S\Rightarrow_{(j}^{*}\tau_{1}C^{i}SC^{j}\tau_{2}$$\tau_{1},\tau_{2}\in(T\cup\{C^{m}\})^{*}$$C^{i}SC^{j}\Rightarrow r$$\Rightarrow^{*}$$C^{i}C^{i^{r}}{}_{u1}C^{k}SC^{l}f_{1}C^{/}C^{j}\Rightarrow^{*}u_{1}C^{k}SC^{l}c_{1}^{R}$$u_{1}u_{2}\cdots u_{n}uv_{n}^{R}\cdots v_{2}^{R}v_{1}^{R}$$m$$\square$

The following lemmas are obvious from Definition 3.
Theorem 4 For a terminal-cml grammar $G=$$(\{S, C\}, T, P, S),$
string $w\in T^{+}is$ in $L(G)$ , then there
exists a stringwith $n\geq 0$ such
and $[u_{1}|v_{1}]\cdots[u_{n}|v_{n}][u]\in$
that$\{C^{m}\}$Lemma 2 $Ifa$ stringis in $L(M_{G})$ , then is oneof the forms; $[u]$ and $[u_{1}|v_{1}]\cdots[u_{n}|v_{n}][u](n\geq 1)$ .
$\alpha\in\Sigma_{G}^{*}$$0$$\alpha$In the following, for simplicity, we assume that if $n=$then $[u_{1}|v_{1}]\cdots[u_{n}|v_{n}][u]=[u]$ .

$\iota fa$$[u_{1}|v_{1}]\cdots[u_{n}|v_{n}][u]\in\Sigma_{G}^{+}$$w=u_{\mathfrak{l}}\cdots u_{n}uu_{n}^{R}\cdots v_{1}^{R}$$L(M_{G})$.

Proof We will show that for $0\leq i,j<m$ and$w\in T^{+}$ , if there is a derivation
suchtonderived from a terminal-cml grammar
a string
is in $L(M_{G})$, then that terminal ml-productions occur $n+1(n\geq 0)$ times in , then there exists a stringis in $L(G)$ .
and $w=$such that
Proof Consider a terminal-cml grammar $G=$
. We will prove this by induction on$(\{S, C\}, T,P,S)$ and the nondeterministic finite automa. We note that for the case $i=j=0$ , this implies
tonderived from .
Theorem 4.
We will show that if
Base step, $n=0$ : Assume that there is a derivation
then there is a derivation, where $0\leq i,j<m,$ $w\in T^{+}$ , and only one
Theorem 3 For the nondeterministic finite automa$M_{G}$$G,$$\iota f$$C^{i}SC^{j}\Rightarrow\gamma w$$\{C^{m}\}$$[u_{1}|v_{1}]\cdots[u_{n}|v_{n}][u]$$[u_{1}|v_{1}]\cdots[u_{n}|v_{n}][u]$$\gamma$$u_{1}\cdots u_{n}u\iota_{n}^{R}\cdots U_{1}^{R}$$\delta^{*}(q_{i,j}, [u_{1}|v_{1}]\cdots[u_{n}|v_{n}][u])\ni q_{0}$$\{C^{m}\}$$u_{1}\cdots u_{n}uv_{n}^{R}\cdots U_{1}^{R}$$n$$M_{G}=(Q, \Sigma_{G},\delta, q_{0,0}, \{q_{0}\})$$G$$\delta(q_{i,j}, [u_{1}|v_{1}]\cdots[u_{n}|v_{n}][u])\ni q_{0}$$C^{i}SC^{j}\Rightarrow^{*}u_{1}\cdots u_{n}u\#_{n}\cdots v_{1}^{R}$$C^{i}SC^{j}\Rightarrow\gamma w$

148, conderived from . Based onterminal ml-production occurs in . Then, the terminal$Sarrow C^{i’}wC^{j}$with $i=(m-i’)mod m$ stmct a linear grammar $G_{l}=(N, T, P_{l},N_{0.0})$ , where
ml-production is
and $j=(m-j’)mod m$ . By the constmction of , there$\{N_{i,j}|q_{i,j}\in Q|$ ,.
is a transition
Induction step: Assume that there is a derivation.
such that terminal ml-productions occur$n+2$ times in . Let
be the first used terminal mlFrom Theorems 3 and 4, it is obvious that $L(G)=L(G_{l})$ .
production in . There are three cases: $r\in P(1)$ ;$G$$(Q,\Sigma,\delta,q_{0,0}, \{q_{0}\})$$\gamma$$M_{G}$‘$\delta$$N$$=$$P_{l}$$=$$\delta(q_{i,j}, [w])\ni q_{0}$$C^{i}SC^{j}\Rightarrow\gamma w$$\{N_{i,j}arrow uN_{k,l}\iota^{R}|\delta(q_{i,j}, [u|v])\ni q_{k.l})\cup$$\{N_{i,j}arrow u|\delta(q_{i,j}, [u])\ni q_{0}\}$$r$$\gamma$$\gamma$$r\in P(2);r\in P(3)$. We prove only the case $r\in P(1)$ ,$\square$since the proof of other cases is similar to the proof of-cml lanWe will show that the class of terminal
the first case.
incompaguages and the class of regular languages are
Suppose that is $Sarrow C^{i’}uC^{k}SC^{l}v^{R}C^{j’}$ in $P(1)$ . rable.
Then, there exists a derivation
Theorem 6 For a given integer $m\geq 2,$ $t-CML_{(C^{m}|}$ and$REG$ are incomparable.
$\{C^{m})$$r$$C^{i}SC^{j}\Rightarrow r$$\Rightarrow\gamma_{I}$$\Rightarrow\gamma_{2}$$C^{i+i’}uC^{k}SC^{l}\iota^{R}C^{j’+j}$$uC^{k}SC^{l}f$$uw’ \int j^{R}$

Proof Since ML and REG are incomparable ([2]) and, it suffices to show that
ML is incIuded inthere exists a regular language that is not a terminal,$t-CML_{(C^{\hslash l}|}$such that $uw^{\prime f}=w$, only the c-production is applied in, and ml-productions occur $n+1$ times in .
-cml language.
Since only the c-production is applied in , it folConsider a regular language. By
Iows from the definition of that.
, there exthe induction hypothesis and,ists a stringsuch that-cml grammar
Assume that there is a terminalHence,, and.
$G=(\{S, C\}, T,P,S)$ such that
hold.
and
be theand $L_{r}=L(G)$ . Let
nondeterministic finite automaton derived from .
is a subFor each $l(0\leq 1\leq 2m^{2})$ , since
3.3 Linear languages and regular langua- set of , it follows from Theorem 3 and $L_{r}=L(G)$ thatsuch thatand integers
there exist a stateges
and at least one of and is greater
We show that the class of linear languages properly than . Similarly, if there exist strings $u,v\in T^{*}$ such-cml languages.
includes the class ofterminal, thenare suband
that
$w\in
L_{r}$$i_{l}>0$(resp. $j_{l}>0$ ). Hence, if
strings of some
Theorem 5 For a given integer $m\geq 2$ , every terminal
then (resp. v) is a sequence of al. Therefore, if-cml language is linear.
, then bothandhold. This imand
Proof For a terminal-cml grammar , con- plies that there exist no three mutually distinct integers.
andsuch thatsider a nondeterministic finite automaton$\lceil(2m^{2}+1)/2\rceil=m^{2}+1$
staThat is,must have at leasttes except for the final state, whereas consists of$\gamma_{2}$$7\downarrow$$\{C^{m}\}$$\gamma_{1}$$\delta$$\delta(q_{i,j}, [u|v])\ni q_{k.l}$$C^{k}SC^{l}\Rightarrow\gamma_{2}w’$$L_{r}=\{(a_{0})^{h)}(a_{1})^{k_{1}}\cdots(a_{2m^{2}})^{k_{-m^{2}}}|k_{0},k_{1}, --, k_{2m^{2}}\geq 0\}$$\alpha=[u_{1}|v_{1}]\cdots[u_{n}|v_{n}][u’]$$a\in\Sigma_{G}^{+}$$\{C^{m}|$$\delta^{*}(q_{k,l},\alpha)\ni q_{0}$$w’=u_{1}\cdots u_{n}u’c_{n}^{R\ldots f_{1}}$$T=\{a_{0},a_{1}, \ldots,a_{2m^{\sim}}\}$$\delta^{*}(q_{ij}, [u|v]a)\ni q_{0}$$w=uu_{1}\cdots u_{n}u’\iota_{n}^{R\ldots f_{1^{U^{R}}}}$$M_{G}=(Q,\Sigma_{G},\delta, q_{0,0}, \{q_{0}\})$$\square$$G$$\{(a_{l})^{k}|k\geq 0\}$$L_{r}$$i_{l},j_{l}\geq 0$$\hat{q\tau}\in Q$$\delta\cdot(\overline{q_{l}}, [a_{l}^{i_{l}}|a_{l}’’])\ni\overline{q_{l}}$$j_{l}$$i_{l}$$0$$\{C^{m})$$\delta^{*}(\overline{q_{l}}, [u|\iota^{R}])\ni\overline{q_{l}}$$a_{l}^{i,}ua_{l}^{i_{l}}$$\sigma_{l}’’va_{l}’’$$\overline{q_{l_{1}}}=\hat{q_{l_{2}}}$$u$$\{C^{m}\}$$l_{1}<l_{2}$$\{C^{m}\}$$j_{l_{1}}=0$$i_{l_{2}}=0$$G$$l_{1},$$M_{G}$$l_{2},$$0\leq l_{1},$ $l_{2},$ $l_{3}\leq 2m^{2}$$l_{3}$$\overline{q_{l_{I}}}=\overline{q_{l_{2}}}=\hat{q_{l_{3}}}$$=$$M_{G}$$Q$$m^{2}$

149
states except for the final state. This is a contradiction.
Therefore,
is not a terminal-cml language.
$L_{r}$$\{C^{m}\}$where$\square$$P_{l}’$$=$

Since REG is included in LIN, the following proper
inclusion follows from Theorems 5 and 6.

4$\{C^{*}\}$$=$$\{Sarrow C^{X}SC^{q}\tau C^{n-p}|$$x=(n+q-p)mod n\}$,$N_{p}arrow N_{q}\tau\in P$$t-CML_{\{C^{m}\}}\subset$-cml languages

We consider the union ofin this section.

$y=(n+q-p)mod n\}$,$N_{p}arrow\tau N_{q}\in P$$P_{r}’$

Theorem 7 For a given integer $m\geq 2,$$LIN$.

$\{Sarrow C^{n-p}\tau C^{q}SC^{y}|$$P_{f}’$$=$$\{Sarrow C^{n-p}\tau C^{n-p}|N_{p}arrow\tau\in P\}$

$P_{C}$$=$$\{C^{n}arrow\epsilon\}$.

We will show that for any $z\in T^{+}$ and any $N_{p}\in N$ , there$t-CML_{\{C^{nt}|}$is a derivation : $N_{p}=^{\phi}cz$ if and only if there is a
derivation :. Note that for the case
$p=0$ , this implies that a string is in $L(G)$ if and only
ifz is in $L(G’)$ .

over all $m\geq 1$$\phi$$C^{p}SC^{p}=^{\gamma}c^{t}z$$\gamma$$z$

Definition 4 A language
is a)-cml language)(resp. terminal-cml language
there is some inpart : We use induction on the length of .
$m\geq1$$\{C^{m}\}-cml$
tegersuch that is alanguage (resp.
Base step, $k=1$ : Assume that there is a derivation :terminal-cml language). Let $CML_{\{C|}$ (resp. t, where $N_{p}\in N$ and $z\in T^{+}$ . For a production$CML_{|C|})$ be the classof $\{C^{*}|-cml$ languages (resp. ter- $N_{p}arrow z$ in , from the constmction of , there is aminal
-cml languages).
production : $Sarrow C^{n-p}zC^{n-p}$ in $P’$ . Therefore, there
is a derivation.
From Definition 4 and Theorem 5, the following are
Induction step: Consider a derivation:
obvious.
$\alpha=_{G}^{*}z$ , where the length ofis $k+1,$ $N_{p}\in N$,$z\in T^{+}$ , and $r\in P$ . There are twocases for $r:(1)r$ is
t-CML $\{C^{m}|=t$-CML
LIN.
, and (2) is1. We prove only the
Lemma 3 A linear language is a terminal $\{C^{*}\}-cml$ firstcase,
Isince the proof of the second case is similar
language.
to the proofof the first case.
Then, the derivation
becomes:
Proof Consider a linear language $L=L(G)$ , where 1. For the production , from the con$G=(N, T, P,N_{0})$ and $N=\{N_{0}, \cdots,N_{n-1}\}$ . Without loss
stmction of , a production: $Sarrow C^{n-p}\tau C^{q}SC^{y}$of generality, we may assume that any production in$P’$ ,
is in
where $y=(n+q-p)mod n$ . For a derivais one of the forms, tion $N_{q}=_{G}^{*}z’$ , from the induction
hypothesis, there$N_{q}\in N$.
where
and
Therefore,.
is a derivation
there isWe constmct a terminal-cml grammar $G’=$aa derivation$(\{S, C\}, T,P’,S)$ as follows: $P’=P_{l}’\cup P_{r}’\cup P_{f}’\cup P_{C}$ ,, where7
is a sequence of the cproduction.
$L$$\{C^{*}$$\{C^{*} \}$$[Only-\ddagger f$$\iota f$

$k$

$]$

$L$

$\phi$$\delta$$\{C^{m}\}$$N_{p}\Rightarrow c^{z}$$P$$\{C^{*}\}$$]$$P_{f}’$$r$$i$$C^{p}SC^{p}=^{r}c^{J}C^{p}C^{n-p}zC^{n-p}C^{p}\Rightarrow_{G_{\gamma}}^{*},z$$N_{p}\Rightarrow G$$\phi$$\phi$$‘$$\dot{A}$$\bigcup_{m\geq 1}$$|C.|\subseteq$$N_{p}arrow\tau N_{q}$$r$$N_{p}arrow N_{q}\tau$$t$$\phi$$\phi$$\tau N_{q}\Rightarrow_{c}^{*}\tau z’=z$$\llcorner\sigma$$N_{p}$$\Rightarrow Gr$

$r$

$r’$

$P_{l}’$$P$$i$$N_{p}arrow\tau N_{q},$ $N_{p}arrow N_{q}\tau,$ $N_{p}arrow\tau$$t$$\tau\in T^{+}$$N_{p},$$i$$C^{q}SC^{q}\Rightarrow_{G}^{*},$$z’$$\{C^{n}\}$$C^{p}SC^{p}=^{r’}c’C^{p}C^{n-p}\tau C^{q}SC^{y}C^{p}\Rightarrow G’\sigma_{c}$$\tau C^{q}SC^{q}\Rightarrow_{c}^{*},$$\tau z’$$\sigma_{c}$$1$[If part]: We use induction on the number
$[$

$k$

of ml-

productions that occur in .
Base step, $k=1$ : Assume that there is a derivation: $C^{p}SC^{p}=_{G}^{*},$ , where $0\leq p<n,$ $z\in T^{+}$ , and only$r$$\gamma$$\gamma$$z$

150
one ml-production occurs in . Then, the ml-production
is : $Sarrow C^{n-p}zC^{n-p}$ . Since is in , it follows from$\gamma$$r$$r$$P_{f}$

the constmction of $P’$ that $N_{p}arrow z$ is in

there is a derivation
Induction step:$N_{p}\Rightarrow cz$$P$. Therefore,.

:
Consider a derivation, where is an ml-production,$\gamma$$C^{P}SC^{P}=^{r}c’\alpha\Rightarrow G’\gamma_{1}z$ml-productions occur$r$times in $\gamma_{1},0\leq p<n$ , and. There are two cases for $r:(1)r\in P_{l}’;(2)r\in$ P..
We prove only the first case, since the proof of the second case is similar to the proof ofthe first case.
. Then, it follows from the definition ofLet$y=(n+q-p)mod n$ ,that is$\in P$ .
Hence, the derivationisand. Therefore, there is a derivationsuch that:
ml-productions occur times in . From the induction. Therefore,
hypothesis, there is a derivation
ロ.
there is a derivation$k$$z\in T^{+}$$P_{l}$$r\in P_{l}’$Fig. 1: Language hierarchy$Sarrow C^{n-p}\tau C^{q}SC^{y},$$r$$N_{p}$$arrow N_{q}$$\gamma$$]$$C^{p}SC^{P}=^{r}G’C^{P}C^{n-p}\tau C^{q}SC^{y}C^{p}\Rightarrow G^{;TZ’}7|=z$$C^{q}SC^{q}\Rightarrow_{G’}\nearrow\gamma_{2}$$\gamma_{2}$$k$$\gamma_{2}$$N_{q}\Rightarrow_{G}^{*}z’$[1] V.Geffert. Normal forms for phrase-stmcture

grammars. Theoretical Infomatics and Applications, RAIRO, 25, 5, pp.473-496, 199].

$N_{p}\Rightarrow_{G}\tau N_{q}\Rightarrow_{G}^{*}\tau z’=z$

From Lemma 3, we have the following theorem.
Theorem 8 $t-CML_{|C|}=LIN$.

In this paper, we considered the generative powers $of$
terminal cancel minimal linear grammars with a uniquenonterminal symbol except . Figure 1 shows the re$S$

sults proved in this paper.
Geffert [1] shows other types of cml grammars, forexample,(1) $P_{C}=\{ABarrow\epsilon,$ $BBBarrow\epsilon\downarrow N_{C}=\{A,$ $B|$ ,,(2) $P_{C}=\{ABBBAarrow\epsilon\}$ ,$N_{C}=\{A, B\}$

(3) $P_{C}=\{ABarrow\epsilon,CDarrow\epsilon\}$ ,$N_{C}=\{A, B,C,D\}$ ,(4),$N_{C}=\{A, B, C\}$.

The question of deciding generative powers of cml
grammars with two or more nonterminal symbols except is open and of great interest to be smdied.
$S$zations of recursively enumerable languages withvery small language classes. Theoretical Computer Science, 250, pp.55-69, 2001.
[3] K.Onodera. On the generative powers of some

5 Concluding Remarks$P_{C}=\{ABCarrow\epsilon\}$[2] S.Okawa and S.Hirose. Homomorphic characteri-extensions of minimal linear grammars. IEICE
Trans. $Inf$ &SYS., E90-D, pp. 895-904, 2007.
[4] G.Rozenberg and A.Salomaa, Eds. Handbook ofFormal Languages. Springer, 1997.