数理解析研究所講究録
第 716 巻 1990 年 60-70

60
On Learning A Class of Context-free Languages
in Polynomial Time横森貴

Takashi YOKOMORI
Department of Comput er Science
Un iversity of Electro-Comm unica tions
1-5-1 Chofugaoka, Chofu, Tokyo 182, JAPAN

Abstract. The problem of learning context-free languages is studied, in which a subclasscalled c-deterministic context-free languages is introduced. The class of c-deterministic
context-free languages properly contains the class of regular sets.
It is shown that the class of c-deterministic context-free languages is learnable inpolynomial time from membership queries and equivalence queries, that is, it is polynomial
time learnable from so-called minimally adequate teacher.

1

Introduction

We consider the problem of learning a class of context-free grammars. The problemof learning a “correct” grammar for the unknown language from finite examples of thelanguage is known as the grammatical inference problem.
The grammatical inference problem is one of the most attractive issues in many AI
areas in that it may bring us fruitful implications in the field of machine learning suchas syntactic pattern recognition and automatic program synthsis. Most of the existing
practical methods can, however, only solve the problem for the class of regular sets andthere are a few studies for more general classes(e.g.,[2], $[5],[7],[9]$ ).
Recently, Angluin gives a polynomial time algorithm for learning regular sets fromequivalence queries and membership queries([2]).
In this paper, we present an algorithm for learning c-deterministic context-free languages from membership queries and equivalence queries (so-called “minimally adequate
teacher”) in polynomial time. Since the class of c-deterministic context-free languages
properly contains the class of regular sets, this gives a generalization of the corresponding
results on regular sets in [2].

2Preliminaries

We assume the reader to be familiar with the rudiments of formal language theory(See,e.g., [4]), and we only give some basic notations and definitions used in this paper.

61

For a given finite alphabet , the set of all strings with finite length (including zero)is denoted by .(An empty string is denoted by ) $lg(w)$ denotes the length of a string.
denotes. A language over is a subset of . For a string inanda languge over , let $x\backslash L=\{y|xy\in L\}(L/x=\{y|yx\in L\})$ . A language
isrespect
to
.
For
any
with
in
,
left(right)$(w)=\{x|xy=w$
calledderivative ofPrefadn
for some } and $Suf(w)=$ { $x|yx=w$ for some }. Let
be languages, then$\Sigma$$\lambda.$$\Sigma^{*}$$\Sigma^{+}$

$w$

$L$

$\Sigma^{*}-\{\lambda\}$$L$$\Sigma$$\Sigma^{*}$$x$$\Sigma^{*}$$x\backslash L(L/x)$$\Sigma$$L$$L_{1}$$y$$y$$\Sigma^{*}$

$w$

$x$

$L_{2}$$L_{1}L_{2}=\{xy|x\in L_{1}, y\in L_{2}\}$A context-free grammar is denoted by $G=(N, \Sigma, P, S)$ , where $N$ and are alphabets of nonterminals and terminals respectively such that $N\cap\Sigma=\phi$ . $P$ is a finite set
is a nonterminal and is a stringof rules : each rule is of the form $Aarrow\alpha$ , where. Finally,
is a special nonterminal called the start symbol.
of symbols from, then we may write
and and are any strings in
If $Aarrow\beta$ is a rule of. The notationis the reflexive and transitive closure of
(The
) For
is abbreviated when it is clear from the context and is written
subscript. In particular, $L(S)$ , denoted by $L(G)$ , is called, let
the language generated by . A language is context-free if there exists a context-freegrammar such that $L=L(G)$ .
sometimes abbreviate context-free grammars and their languages as CFGs and
CFLs, respectively.
Since we are concern $ed$ with the learning problem of context-free grammars, without
loss of generality, we restrict our consideration to only A-free context-free grammars.
A context-free grammar $G=(N, \Sigma, P, S)$ is 2-standard form if each rule is of one of
the following forms: $Aarrow aBC,$ $Aarrow aB,$ $Aarrow a$ , where $A,$ $B,$ are nonterminals andis a terminal symbol. A $CFGG$ is reduced if (1) for any $A,$ $B\in N,$ $L(A)\neq L(B),$ (2) forand.
any $A\in N$ , there are derivations such thatis a -free, reduced $CFG$ in
In what follows, we may assume that any grammar$relation\Rightarrow
indicates$
the left-most one.
2-standard form. Further, a derivation by the$\Sigma$$A$$\alpha$$S$$(N\cup\Sigma)^{*}$$P$$\alpha$$(N\cup\Sigma)^{*}$$\gamma$$\Rightarrow^{G*}$$\alpha A\gamma\Rightarrow^{G}\alpha\beta\gamma$$\Rightarrow G$$G$$\alpha\in N^{+}$$as\Rightarrow.$$L(\alpha)=\{x\in\Sigma^{*}|\alpha\Rightarrow^{G*}x\}$
$G$

$L$

$G$

$\backslash 1^{\gamma}e$$C$$A\Rightarrow^{*}w(w\in\Sigma^{*})$$S\Rightarrow^{*}\alpha A\beta$

$G$

2.1

$a$

$\lambda$

An Example, where $au$ is a
Let $G=(N, \Sigma, P, S)$ be a $CFG$ . For each $A\in N$ , let$Aarrow a\alpha$is called shortest rule ofshortest terminal string derivable from . Then, a rule
$A\Rightarrow a\alpha\Rightarrow^{*}au\in\Sigma^{*}$

$A$

$A$

.

as follows: [step 1] For eachWith a given $CFGG$ , we can associate a finite graph, connect a node with a node by an arrow labelled . ( is called starting, then introduce a new special symbol called final node and connect with
node. Ifit.) [step ] Let $\alpha=Au(A\in N, u\in N^{*})$ be a node created at step (i-l). Then, apply
to each cv the following procedure: If does not appear yet as the left-most nonterminaland connectof any node created previously, then for each $Aarrow b\beta$ , create a node
, corressponding
with it by an arrow labelled . Otherwise, connect with the nodeis , thento the right-hand side of a shortest rule $Aarrow b\beta$ , by an arrow labelled . (If$\alpha(=A)$
with the final node.) Let be $i+1$ and repeat step until the procedureconnect
cannot be applicable to any node.
$C_{G}$$Sarrow a\alpha\in P$

$S$

$S$

$a$

$\alpha$$S$$\alpha=\lambda$

$i$

$A$

$\beta u$$b$$\beta u$$\alpha$

$b$

$i$

$i$

2

$\alpha$$\beta u$$\lambda$

62

It is easily seen that the procedure terntinates in finte time. The graphis called$G([10])$the characteristic graph of. The graphcontains the complete information on
the grammar , and more importantly, each nonterminal in $N$ is characterized by a finite. Let us see it below.
set of paths in
Take the following $CFG$ as an example for our discussion: $G=(\{S, A, B, C, D\},$ ,} $P,$ ), where $P$ is given by$C_{G}$$C_{G}$$G$$C_{G}$

$\{a$

$S$

$b,$ $c$$,$$Sarrow aAD|aD$ ,$Darrow bCA$,

$Aarrow aAB|aB$$Barrow b$,$Carrow c$.

Note that the language $L(G)$ is $\{a^{m}b^{m}ca^{n}b^{n}|m, n\geq 1\}$ . The characteristic graph of
pictured in Figure 1.
By a simple calculation, we have the following equations:$a\backslash L(S)=$$L(A)L(D)\cup L(D)$$ab\backslash L(S)=$$L(C)L(A)$$abc\backslash L(S)=$$L(A)$$aaab\backslash L(S)=$$L(B)L(D)$$L(D)/bcab=$$\{\lambda\}$

$G$

is

(1)
(2)
(3)
(4)
(5)

Let $L=L(S)$ . Then, from (3)$L(A)=abc\backslash L$

is immediately obtained. Further, from (4) and (5), it holds that
$L(B)=aaab\backslash L/bcab$.

In the same manner,$L(C)=ab\backslash L/ab$$L(D)=aab\backslash L$

are obtained.
Thus, given an $L(=L(G))$ each nonterminal $X$ of is completely characterized by apair $(x, z)$ such that $x\in Pref(w),$ $z\in Suf(w)$ , for some $w\in L$ . That is, each nonterminalof has its own context $(x, z)$ by which it is distinguished from others. This feature willplay a significant role in the process of learning a class of CFGs, and leads us to thefollowing presented in the next section.
$G$

$G$

Notes.
be a shortest terminal string derivable from $X$ , then, for each pair $(x, z)$ such
(1) Letthat $L(X)=x\backslash L/z$ , a string xyxz is always in and is corresponding to a path from.
to the final node in$X\inN$, a pair $(x, z)$ such that $L(X)=x\backslash L/z$ is not necessarily unique. For(2) For each$y_{X}$$L$$C_{G}$

3

$S$

63
example, $L(A)=a\backslash L/bcab(module\lambda)$ .

$Os$$\swarrow^{a}$$\swarrow^{O}aAC\searrow^{b}\otimes AB$$\swarrow a/O^{C}\searrow_{oBc^{a}}^{b}\swarrow$$O$

Figure 1.

2.2

Characteristic Graph$C_{G}$

C-Deterministic CFGs

Let $G=(N, \Sigma, P, S)$ be a $CFG$ . A nonterminal in $N$ is context-deterministic(abb., cdeterministic) iff there is a pair $(x, z)$ such that $S\Rightarrow^{*}xAz(x\in\Sigma^{+}, z\in\Sigma^{*})$ and $L(A)=$. A $CFGG$ is c-deterministic iff each nonterminal in $N$ is c-deterministic. A
language is c-deterministic iff there exists a c-deterministic $CFGG$ such that $L=L(G)$ .
For $A\in N$ , letbe a derivation) with the properties that (1) there is no duplicated application of an identicalrule in the derivation of $x,$ (2)is a shortest string derivable from , and (3)is a
shortest string derivable from .
Let
be the set of triples
of all( is easy to see thatis finite.)
$A$

$A$

$x\backslash L(G)/z$$L$$:S\Rightarrow^{*}xA\alpha\Rightarrow^{*}xy_{A}\alpha\Rightarrow^{*}xy_{A}z_{\alpha}(x,$ $y_{A}\in\Sigma^{+},$$d_{A}$$\Sigma^{*},$$z_{\alpha}\in$$\alpha\in N^{*}$$A$$y_{A}$$z_{\alpha}$$\alpha$$d_{A}s.$$(x, y_{A}, z_{\alpha})$$Q_{A}$$It$$Q_{A}$

Lemma 1 Let $G=(N, \Sigma, P, S)$ be a c-deterministic $CFG$ . Then, for any
such that $L(A)=x\backslash L(G)/z$ .
exists $(x, y_{A}, z)$ in

$A$

in

$N_{f}$

there$Q_{A}$

Proof.

is c-deterministic, for each $A\in N$ , there exists a pair
Let $L=L(G)$ . Since$(x, z)$ such that $L(A)=x\backslash L/z$ and $S\Rightarrow^{*}xAz$ . Let
be a shortest string in $L(A)$ .
$G$$y_{A}$

4

64

Suppose that $(x, y_{A}, z)$ is not in$Q_{A}$, and that

$S\Rightarrow^{*}x’Az’\Rightarrow x’\beta z’\Rightarrow^{*}x’uAvz’=xAz$

It is clear that

, where$u,$ $v,$ $x’,$ $z’\in\Sigma^{*},$ $\beta\in(N\cup\Sigma)^{*}$.

holds, from which we have $u\backslash L(A)/v\subseteq x’u\backslash L/vz’(=$. It is obvious that $L(A)\subseteq u\backslash L(A)/v$ . Hence, $L(A)=u\backslash L(A)/v$ holds.
This implies that for $u,$ above, there is no other derivation such that, for sone$\alpha(\neq A)\in N^{+}$ . Hence, if there is an application of the rule $Aarrow\beta$ during the derivation
process from to $x’Az’$ , one may replace $x’Az’$ with $x”Az$ “ (such that$x”uAvz”$ and $lg(x’z’)>lg(x’’z’’))$ so that $x”u\backslash L/vz^{;/}=L(A)$ holds.
In this manner, after applying the above procedure repeatedly, we eventually obtain apair $(x’, z’)$ such that, besides $L(A)=x’\backslash L/z’$ , a triple $(x’, y_{A}, z’)$ satisfies the requirementsof .
$L(A)\subseteq x’\backslash L/z’$$x\backslash L/z=L(A))$$A\Rightarrow^{*}u\alpha v$

$v$

$S$

$d_{A}$$S\Rightarrow^{*}x’’Az’’\Rightarrow^{*}$$\square$Further, as shown below, the set QA is obtained from the characteristic graph of thegrammar at issue.
Lemma 2 Letbe the characteristic graph of a $CFGG=(N, \Sigma, P, S)$ . Then, without
counting self-looping, the length of a path inis less than $2|P|^{2}+|P|$ , where $|P|$ is the
cardinarity of .
$C_{G}$$C_{G}$$P$

Proof.

From the definition ofand the property of a gramm $ar$ in 2-standard form,
the length of the longest path is less than $|N|(2t+1)$ , where $|N|$ is the cardinality of $N$ ,is a shortest string in $L(A)$ }. Since $|N|\leq|P|$ and $t\leq|P|$ , the longest{$t=_{A} \max_{\in N}$$C_{G}$$y_{A}|y_{A}$path is bounded by $2|P|^{2}+|P|$ in length.

$\square$

Let $t_{G}=2|P|^{2}+|P|$ and $R_{G}=\{w\in L(G)|lg(w)\leq t_{G}\}$ . Furhter, let be in
such
$(x,$
$(w)$
$z)|x,$
that $lg(w)\geq 2$ . Then, Non
is defined as {and $xyz=w$ }.
Finally, let $NT(G)= \bigcup_{w\in R_{G}}Non(w)$ .
$\Sigma^{*}$$w$$y\in\Sigma^{+},$ $z\in\Sigma^{*}$$y,$in $N$ of a c-deterministic $CFGG$ , there is a triple $(x, y, z)$ in
Lemma 3 For any$NT(G)$ such that $L(A)=x\backslash L(G)/z$ .
$A$

Proof.

, each triple $(x, y, z)$ in QA just corresponds to
From the way of constructing. Hence, QA is a subset of $NT(G)$ .
a string associated with each path in$C_{G}$$\square$$C_{G}$

and $L(G)$ , canThis guarantees that the set $NT(G)$ , depending only on the size
provide complete information on all nonterminals of , which implies that nonterminal
membership queries are replaceable in terms of membership queries to an appropriate
subset of $NT(G)$ , as discussed below.
$t_{G}$

$G$

5

65
3

Learning CFGs

3.1

Learning Protocols

Let be a target $CFL$ over a fixed alphabet . We assume the following types of queries
in the learning process. A membership query proposes a string
and asks whether$x\in L$ or not. The answer is either yes or no.
An equivalence query proposes a grammar
and asks whether $L=L(G)$ or not.
The answer is yes or $no$ , and in the latter case together with a counterexample in thesymmetric difference of and $L(G)$ . ’A counterexample is positive if it is in $L-L(G)$ ,and negative otherwise.
The learning protocol consisting of membership queries and equivalence queries iscalled minimally adequate teacher.
The purpose of the learning is to find a $CFGG=(N, \Sigma, P, S)$ such that $L=L(G)$with the help of minimally adequate teacher.
In [1], Angluin employs a strong query called nonterminal membership queries which,and a nonterminal of with unknown et of rules $P$ , can ask
given a string
whether $x\in L(A)$ or not, and the answer is yes or $no$ . The primary issue here is how
one can replace nonterminal membership queries by membership queries at the sacrificeof some sort of restriction.
$L$$\Sigma$$x\in\Sigma^{*}$

$G$

$w$

$L$

$w$

$A$

$x\in\Sigma^{*}$

$G$

$s$

Diagnosing Rules

3.2

Let $G=(N, \Sigma, P, S)$ be a $CFG$ , where $N=\{A_{1}(=S), \ldots, A_{n}\}$ . A replacement is a finite$B_{i}\in N$ . For
is compatible with
, wheretuple
is compatible
Suppose
exist
such
that
.
ther
iff
, is a terminal string obtained fromwith . Then, an instance of by , denoted byawith terminal string .
by replacing each occurrence of(not neccessarily from of ) is incorrect for $L(G)$ iff there exists
A rule$\sigma=[(y_{1},B_{1}), \ldots, (y_{t}, B_{t})]$ which is compatible withsuch that, for eacha replacement$y_{i}\in L(B_{i})$ and. A rule is correct for $L(G)$ iff it is not incorrect$i=1,$
for $L(G)$ . Note that each rule of is correct for $L(G)$ .
The diagnosis procedure is essentially the same as Angluin’s one([l]) and a special casefor a conjectured grammarof Shapiro’s one([6]). The input is a correct parse tree
yield
the
tree not in L. (That is,
root,
the
label
is
the
of
stringoftheissuch thatis a negative counterexample to . The output is a rule that is incorrect for .
. If the child
The diagnosis procedure considers in turn each child of the root ofis labelled with nonterminal $B$ and has a yield , then the procedure tests if is in $L(B)$or not. If the answer is $no$ , then it calls itself recursively with the sub-parse tree rooted. If all theat the child. If the answer is yes, then it goes on the next child of theat the top
queries are answered yes, then the diagnosis procedure returns the ruleisfor.
incorrect, whichof$\sigma$$[(y_{1}, B_{1}), \ldots, (y_{t}, B_{t})]$$e$$\beta$$x_{0},$$\beta=x_{0}B_{1}x_{1}B_{2}\cdots B_{t}x_{t}$$x_{t}\in\Sigma^{*}$$\ldots,$$\beta$$\beta$$\beta\in(N\cup\Sigma)^{*},$$y_{i}\in\Sigma^{*},$$\sigma$$\sigma[\beta]$$\sigma$$B_{i}$$\beta$$\sigma$$Aarrow\alpha$$y_{i}$$P$$G$$\alpha$$\ldots,$$t,$$\sigma[\alpha]\not\in L(A)$

$P$

$G$

$T_{A,w}$

$A$

$w$

$w$

$L$

$L$

$T_{A,w}$

$x$

$x$

$T_{A,w}$$Aarrow\alpha$$T_{A,w}$

$L$

6

66
3.3

Producing Candidate Rules

Let $G=(N, \Sigma, P, S)$ be a (conjectured) grammar obtained in the learning process. Whenever a new positive counterexample is given, the set of nonterminals $N$ is updated as follows: $N$ $:=N\cup Non(w)$ . Further, construct $P_{new}=\{Aarrow a\alpha|a\in\Sigma,$ $lg(\alpha)\leq 2,$,
andcontains at least one new $e1e$ ment of $N$ }. Then, let $P$ $:=P\cup P_{new}$ .
Note that through Section 3 the similar kind of argument can be found in the context
of learning simple deterministic languages in [3].
$w$$A\alpha\in N^{+}$$A\alpha$

3.4

Learning Algorithm[Algorithm $A$ ]Input: a c-deterministic $CFLL$ over .
Output: a $CFGG$ in 2-standard normal form such that $L=L(G)$ ;$\Sigma$

Procedure:
set $G=(\{S\}, \Sigma, P, S))$ , where $P=\phi$ ;repeatmake an equivalence query to ;If the answer is a positive counterexample , thenintroduce new nonterminals from and add them to $N$ ;add all candidate rules to $P$ ;else if the anwer is a negative counterexample , thendiagnose $P$ of ;remove an incorrect rule from ;until the answer of the equivalence query is yes
output and halt.
$G$

$w$

$w$

$w$

$G$

$P$

$G$

The correctness of the algorithm A is based on the principle so-called contradiction
backtracing algorithm originally discussed in [6]. Papers [1] and [3] apply this principle inthe context of derivation process of a context-free grammar.
Important facts are 1) whenever a positive counterexample is given, at least one triple
corresponding to new nonterminal (not in the conjectured gramm r) is introduced, and2) whenever a negative counterexample is given, at least one rule incorrect for $L(G_{0})$ ofis removed from the conjectured grammar.
a correct grammar
$a$

$a$

$G_{0}$

Theorem 4 Given a c-deterministic context-free language over a fixed
A halts and outputs a context-free grammar such that $L=L(G)$ .
$L$$\Sigma_{f}$the algorithm

$G$

3.5

Time Efficiency

Suppose $G_{0}=(N_{0}, \Sigma, P_{0}, S)$ is a c-deterministic $CFG$ such that $L=L(G_{0})$ . The size ofis defined by $|N_{0}|+|P_{0}|$ .
$G_{0}$

7

6*?

the number of elements of Non $(w)$ is
Lemma 5 For a given positive counterexample
at most- $lg(w)(lg(w)-1)$ , and hence, is computable in time polynomial in $lg(w)$ .
$w_{f}$

Proof.

Easy and omitted.

$\square$Lemma 6 The number of required positive counterexamples is at most

Proof.

$|N_{0}|$.

From the property of the algorithm , it is not until new nonterminals arenecessary to derive a string in the target language that a positive counterexample iscounterexample is given, the conjectured grammar
given. Further, whenever agains at least one new nonterminal $(x, y, z)$ corresponding to a nonterminal in , whichis assured by Lemma 3. Thus, the number of required positive counterexamples is not.
greater than
$A$

$L$

$positi_{Ve}^{\backslash }$$A$$|N_{0}|$$N_{0}$$\square$Lemma 7 The number of triples introduced as nonterminals by the algorithm is bounded
whereis the maximum length of positive counterexamples.
by$A$$\frac{1}{2}|N_{0}|m_{p}(m_{p}-1)_{f}$$m_{p}$

Proof.

is given, at mostFrom Lemma 5, each time a positive counterexample
number of nonterminals is introduced. Hence, from Lemma 6, the total
number of nonterminals (triples) introduced in the entire process of leanrnig is boundedis the maximum length of positive.
, whereby$w$$\frac{1}{2}lg(w)(lg(w)-1)$$\square$$\frac{1}{2}|N_{0}|m_{p}(m_{p}-1)$$m_{p}$

Theorem 8 The running time of the algorithm is bounded by a polynomial in the sizeof and the maximum length of counterexamples.
$A$$G_{0}$

Proof.

The algorithm relies on three subrocedures,. $i.e.$ , the computation of candidate
rules, parsing, and diagnosis.
(a) Comutation of candidate rules: Note that a conjectured grammar is asummed to bein 2-standard form. From Lemma 7, the total number $r_{L}(|N_{0}|, m_{p})$ of rules constructedin the entire $pro$ cess of learning is bounded by:
$G$

$L$

$p(|N_{0}|, m_{p})\cross|\Sigma|\cross(p(|N_{0}|, m_{p})+1)^{2}$, where$p(x, y)= \frac{1}{2}xy(y-1)$.

(b) Parsing: It is well known that there exists an algorithm which, given a $CFGG$
in time proportional to $|G|lg(w)^{3}(e,g$ ,and a string in $L(G)$ , produces a parse tree[4]). Since $|G|=|N|+|P|\leq p(N_{0}, m_{p})+r_{L}(|N_{0}|, m_{p})$ , each parsing requires at most
$T_{S,w}$$w$$(p(N_{0}, m_{p})+r_{L}(|N_{0}|, m_{p}))m_{n}^{3}$.

, there are at most $lg(w)$ nonterminals appearing(c) Diagnosis: Given a parse tree
in it. Hence, the diagnosis procedure makes at most $lg(w)(\leq m_{n})$ membership queries inorder to find rule incorrect for $L(G_{0})$ .
times when positive counterexamples are provided. EachNow, there are at mostoftime a negative counterexample is provided, one incorrect rule is removed fromcounterexamplesofnegativethenumberimpliesthat.
Thisgrammarconjecturedarequired is not greater than $r_{L}(|N_{0}|, m_{p})$ .
$T_{S,w}$$a$$|N_{0}|$

$P$

$G$

8

68

Thus, the total time the algorithm A requires is bounded by:$N_{0}\cross r_{L}(|N_{0}|, m_{p})+r_{L}(|N_{0}|, m_{p})\cross\{(p(N_{0}, m_{p})+r_{L}(|N_{0}|, m_{p}))m_{n}^{3}+m_{n}\}$$\leq|G_{0}|r_{L}(|G_{0}|, m_{c})+r_{L}(|G_{0}|, m_{c})\{(p(|G_{0}|, m_{c})+r_{L}(|G_{0}|,m_{c}))m_{c}^{3}+m_{c}\}$where $m_{c}=j\psi ax\{m_{p}, m_{n}\}$ is the maximum length of counterexamples.

3.6$\square$

Implications

Let $G=(N, \Sigma, P, S)$ be a $CFG$ . A nonterminal
in $N$ is harmonic iff $S\Rightarrow^{*}uAv$
and $S\Rightarrow^{*}u’Av’$ imply $u\backslash L(G)/v=u’\backslash L(G)/v’$ . A $CFGG$ is harmonic iff so is eachnonterminal in $N$ . A language is harmonic iff there exists a harmonic $CFGG$ suchthat $L=L(G)([8])$ .
$A$

$A$

$L$

Lemma 9 A harmonic linear $CFL$ is c-deterministic.

Proof.

be a language such that $L=L(G)$ for some harmonic linear $CFG$$G=(N,\Sigma, P, S)$ . Without loss of generality, we may assume that for each $A(\neq S)\in N$ ,every rule with the nonterminal in the left-side is of one of the forms:
Let

$L$

$A$

$Aarrow\alpha A\beta,$ $Aarrow\alpha’B\beta’,$$Aarrow w$, and $B$ derives no string containing . Hence, forwhere $A,$ $B\in N,$ , of,each $A\in N,$ $L(A)$ is infinite.
We claim that can be modified to have the property that
iff
imply that $L(A)=L(B)$ .
iff
and that $L(A)\neq L(B)$ .
Suppose otherwise, i.e.,,(Note that both $L(A)$ and $L(B)$ are infinite.) It is easy to see that since$S\Rightarrow^{*}xAy$ iff $S\Rightarrow^{*}xBy$ , each recursive rule
must be exactly correspondingof and $\beta=\beta’$ . For the same reason, it must hold a nonto $Barrow\alpha’B\beta’$ , i.e.,
is in $P$ . By introducing new nonterminal
is in iffrecursive rule$[A, B]$ , merge each two corresponding rules into one new rule $[A, B]arrow\alpha[A, B]\beta$ andremove old rules. Further, for all of other non-recursive rules $Aarrow\gamma(Barrow\gamma’)$ , remove
and $B$ inthem and add $[A, B]arrow\gamma|\gamma’$ . Then, with $[A, B]$ replace all occurrence ofthe right-side of rules. After applying the above procedure to all pairs of nonterminals
inconsistent to the claim, the resulting grammar clearly satisfies the requiremet of theclaim. This construction preserves the equivalence of the resulting grammar to the original
one, including the harmonicity.
$v\in$
Hence, we have an equivalent harmonic linear grammar with the property that
$S\Rightarrow^{*}uBv$ ] implies that $L(A)=L(B)$ .
$S\Rightarrow^{*}uAv$, if
Thus, foriff[
$x\backslash
L/z=L(A)$.
, then$\alpha$$\beta,$$\beta’,$$w\in\Sigma^{*}$

$A$

$G$

$\forall x,y\in\Sigma^{*},$$S\Rightarrow^{*}xAy$$S\Rightarrow^{*}xBy$$\forall x,$$y\in\Sigma^{*},$$S\Rightarrow^{*}xAy$$S\Rightarrow^{*}xBy$$\forall x,$$y\in\Sigma^{*}$$Aarrow\alpha A\beta$$\alpha=$$Aarrow\alpha B\beta$$P$$Barrow\alpha A\beta$$A$$\forall u,$$\forall x,$$\Sigma^{*}$$S\Rightarrow^{*}xAz$$z\in\Sigma^{*}$$\square$Corollary 10 The class of harmonic linear CFLs is polynomial time learnable from $\min-$imally adequate teacher.
969Note that since the class of harmonic linear CFLs properly contains the class ofregular sets, the class of c-deterministic CFLs properly contains the class of regular sets.
A $CFGG=(N, \Sigma, P, S)$ is simple deterministic(abb., $SD$ ) iff $Aarrow a\alpha$ and $Aarrow a\beta$
are in imply that $\alpha=\beta([4])$ . A nonterminal in $N$ is suffix-free iff is in $L(A)$ implies
that for all $y\in Suf(x)-\{x\}y$ is not in $L(A)$ . A $CFGG$ is suffix-free iff so is eachnonterminal in $N$ .
$P$

$A$

$x$

$A$

Lemma 11 A suffix-free $SDGG=(N, \Sigma, P, S)$ is c-deterministic.

Proof.

Since

From the property of SDGs, it holds that if, then $L(A\alpha)=x\backslash L$ .
is suffix-free,
is suffix-free. Hence, let be a string in, then $L(A)=$iS obtained. 口$S\Rightarrow^{*}xA\alpha$$G$$x\backslash L/w$

$L(\alpha)$$w$$L(\alpha)$

Corollary 12 The class of suffix-free SDLs is polynomial time learnable from minimallyadequate teacher.

4

Discussions

NVe have presented an algorithm for learning a class of context-free languages from minimally adequate teacher, which is based on the characterization results of nonterminals
using derivatives of a target language. The class of c-deterministic CFGs has been targeted, and it was shown the algorithm learns a correct grammar in polynomial time fromminimally adequate teacher, which gives a generalization of the corresponding result on
regular sets in [2].
However, it should be mentioned that the definition of a minimally adequate teacher
in this paper is slightly different from the original one by Angluin ([2]) in that the latterassumes the class of conjectures to be the same type as target class(i.e., both classes
comprise finite-state automata and their regular sets, respectively), while the former allows
arbitrary CFGs in 2-standard form as conjectures in order to learn a subclass of CFLs
called c-deterministic. This kind of teacher is called extended minimally adequate teacher
in [3].
In [8] harmonic linear CFGs are introduced and a complete learning algorithm frompositve and negative examples is given without time analysis, which is clearly shown to
be not less than NP-complete from the problem setting. Note that the c-deterministic
language in ection 2.1 is not harmonic linear.
The paper [3] gives a polynomial time algorithm for simple deterministic CFLs fromthe same learning protocol as the one in this paper. When the class of SDLs is targeted,the algorithm in this paper works as a simpler version of the one in [3].
The class of simple deterministic CFLs is incomparable to the class of c-deterministicor harmonic linear CFLs discussed here, and all of them properly contain the class ofregular sets.
$S$

10

70

References[1] D. Angluin. Learning k-bounded context-free grammars. Res.Rep. 557, Dept. ofComput. Sci., YALE Univ., 1987.
[2] D. Angluin. Learning regular sets from queries and counterexampl es.
and Computation, 75:87-106, 1987.

Information[3] H. $Ishizal<a$ . Learning simple deterministic languages. Tech. Rep. 465, ICOT, Tokyo,
1989. Also in Proc. COLT’89.

[4] M.A.Harrison. Introduction to Formal Language Theory. Addison-Wesley, Reading,MA, 1978.
[5] Y. Sakakibara. Learning context-free grammars from structural data in polynomial
time. In Proceedings of 1st Workshop on Computational Learning Theory, pag es 296310, 1988.
[6] E. Shapiro. Inductive inference of theories from facts. Res.Rep. 192, Dept. of Comput. Sci., YALE Univ., 1981.
[7] Y. Takada. Grammatical inference for even linear languages based on control sets.
Information Processing Letters, 28:193-200, 1988.
[8] K. Tanatsugu. A grammatical inference of harmonic linear languages. International
Journal of Computer and Information Sciences, 13:413-423, 1984.

[9] T. Yokomori. Inductive inference of contex-free languages based on context-free
expressions. International Journal of Computer Mathematics, 24:115-140, 1988.
[10] T. Yokomori. Learning simple languages in polynomial time. Tech. Rep., SIG-FAI,
Japanese Society for AI, June, 1988.

11