Inductive Inference of Context-free Languages - Context-free Expression Method

1. Introduction

We consider the following model of inductive inference problem: Given an object L of inference, an inductive inference device (liD) tries to infer a representation H for the object from examples. It is assumed that liD has an enumeration mechanism by which any possible hypothesis froni the representation space can be eventually enumerated at least once. It is also assumed that we can utilize an oracle for presenting examples concerning the object. llD asks the oracle for an example, and computes hypothesis and outputs it, and again asks another example for the next step, and this process is cycled. In a sequence of hypotheses H1. H2, ... llD is said to identify Lin the limit if there exists a positive integer n such that Hn represents Land Hn + i equals to Hn for all i > 0.

A simple algorithm for identification in the limit is the one based on the notion of identification by enumeration. Let HI, H2, ... be an effective enumeration of the possible hypotheses, and suppose a set of examples ei, e2, ... , ek are presented. Then, llD provides as its next output the first hypothesis which is compatible with all these examples. Under the assumption of a perfect oracle, the . sequence of hypotheses converges in the limit.([Gold 1967])

In this paper, we deal with the inductive inference problem for context-free languages, and employ a representation space for hypotheses different from the ones in the existing methods. This enables us to make an elegant discussion on the problem and to obtain a simple algorithm for solving the problem.

2. Context-free Expressions - Extended Regular Expressions

The reader is assumed to be familiar with the rudiments in the formal language theory. (See, e.g., [Salomaa 1973] for definitions not mentioned here.)

For a given finite alphabet :E, the set of all strings with finite length (including zero) is denoted by :E*. (An empty string is denoted by E.) A language L ouer :E is a subset of:E*. For an infinite alphabet r, Lis a language over r ifL is a language over some finite subset :E off.

The following operation plays a crucial role in this paper.

Definition 2.1 ([Gruska 1971])

• (i) Let a be a symbol and LI, L2 be languages. Then, a­ substitution of L2 into L1 , denoted by LI f oL2, is defined as follows:
• LI f oL2 ={XIYl ··· XkYkXk+IIXI a··· XkaXk+tELt, a does not occur in the word Xl ··· Xk+ I and Yi EL2 for 1 ~ i ~k}
• (ii) Let a be a symbol and L be a language. Then, a­ iteration of L, denoted by La, is defined by

Lo={x I x ELUL f oLUL f oL f oLU···, and x has no occurrence of a}.

Remarks.

(l)lfL1 does not contain o, then L1 t aL2 = L1 .

(2)Let L be a language overT and suppose that T does not contain o.

Then, L*=(LoU{t:})o and L+ =(LoUL)o.

We introduce the notion of a context-free expression which provides the representation space for context-free languages.

Definition 2.2([Gruska 1971])

Let r be a (possibly infinite) alphabet, r· be the boldface version off, i.e, f' = {ol aEr}.

• (i) A context-free expressions ouer r are strings over ru r· U{ 4>, +,(,)}defined as follows:
• 4> is a context-free expression,
• if a is in r U{t:}, then a is a context-free expression,
• ifE1. E2 are context-free expressions and a Ef, then (Et + E2), E1E2, (EI)o are context-free expressions,
• nothing else is a context-free expression.

(ii) A mapping II from context-free expressions to a class oflanguages is defined by: ·

1. 14>1 =<I>( empty set)
2. lal ={a}(for 'o' a Ef U{t:})
3. lEI +E2I=IE1IUIE2I, IEIE2I=IEtllE2I, IEoi=IEio.

• (iii) A class oflanguages Q r is defined as foilows:
• «1>, {c} E nr,
• if a E r, then {a}E Or,
• ifL1, Lz E nr and aEr, then L1 ULz, L1L2, and L1°EOr.

Example2.1

Let a,b, a be in r, then E=(aab+ab)o is a context­ free expression. Further, lEI= l<aab + ab)ol = {aab, ab}o ={aibiji;e;1}.0

Now, the next result plays an important role in this paper.

Theorem 2.1 ([Gruska 1971])

Let :E be a finite alphabet, and let L be a language over :E. Then, Lis a context-free language if and only if there exists a finite alphabet T such that :E!;;T and L E nT.

Therefore, we have the following characterization of context-free languages in tenns of context-free expressions.

Theorem2.2

Let :E be a finite alphabet, and let L be a language over :E. Then, L is a context-free language if and only if there exists a finite alphabet T and a context-free expression E overT such that :E!;;T and lEI= L.

Proof. Obvious from Theorem 2.1 and definitions.O

Thus, context-free expressions provide a way of representing context-free languages, and as is shown later, an inductive inference algorithm for context-free languages is obtained by naturally extending the one for regular sets in tenns of regular expressions.

3. Inductive Inference of Context-free Languages

3.1 Inductive Inference Algorithm

In this paper, we formalize the inductive inference problem for context-free languages as follows:

<Inductive Inference Problem for Context-free Languages>

1. a semantic domain D is the class of context-free languages,
2. a target do is a given context-free language,
3. a representation space Q is the class of context-free expressions,
4. an oracle EX() gives a complete presentation of do , that is, for every e E Q such that lel!;;do, EX() eventually returns"+ e" at least once, and for every e E Q such that lel~do, EX() eventually returns" -e "at least once.

Now, let :E be a finite alphabet over which a target context-free language is defined. We fix an infinite alphabet r over which context-free expressions are defined, where :E!;;r.( It is assumed that auxiliary symbols"+","(", and")" are not contained in r.)

We define an operator 8 on Q, the set of all context­ free expressions over r, as follows:

Suppose E, E1. E2 are context-free expressions over r. As a notation, by E1-Ez we denote Ez E 8(E1):

• (1)~-~~
• ~-a (Va ErU{c})
• ~--(~) o (VaEr)
• ~-(~+~)
• ifE1-. E, then E1 + Ez-E + Ez and Ez+E1-Ez+E
• ifE1-E, then E1o-Eo (VaEr)
• ifE1-E, then E1Ez-EEzandEzE1-E2E.

Lemma3.1

The operator 6 defined above has the following properties:

(i) 8 is complete for the most specific expression ~ in the sense that the set 8*(~) of all expressions obtainable from ~ in a finite number of applications of 6 includes at least one expression for every context-free language.

(ii) For arbitrary expressions E1. Ez in Q, whenever E1 E8(Ez), IEzlciE1I holds.

Proof. We prove by induction on the way of constructing expressions in Definition 2.2. (i) It suffices to show that 0!;;8*(~) holds. First, by the rewriting rule (2) above, we have that a E 8(~) for Va ErU{c}. Now, suppose that E1 and Ez are in 8*(~). (In whatfollows, by -· we denote a finite number of applications of-. Then,

~-~+~ ( by (4) ) -· E1 +~ (by applying (5) together with the induction hypothesis)--*EI +Ez (by applying (5) together with the induction hypothesis), thus, we have E1 +Ez E 8*(~). Similarly,

~--~~ (by (1)) --· E1~ (by applying (7) together with the induction hypothesis)--*E1E2 (by applying (7) together with the induction hypothesis),

hence we have E1E2 E 8*(~). Further, ~--~ a ( by (3) ) and since ~--*EI. by applying (6) repeatedly, we have~ o --·E1o, hence ~--*E1o, i.e. E1o E 8*(~).

• (ii) Since, from the rules (1)-(4), 8(~)={~~. c, ~+~.a, ~o(VaEr)}, we have thatfor each E E 8(~), «<> = I~I!;;IEI.

Now, let E' be in 8(E). Then, there are only three cases concerning E.(Note that if E is in ru{c}, then no rule in 6 is applicable to E.)

CD E=E1 +Ez; Let Ei' E 8*(Ei)(i=1,2). Then, by the induction hypothesis, IEilc IEi'l holds. Hence, by (5) lEI =IE1 +Ezl= IE1IuiEzl~ IE1'IuiEzi=IE'I or lEI= IE1 +Ezl= IE1I u IEzl ~ IE1IuiEz'I=IE'I is obtained.

® E =E1E2; By the same hypothesis,

lEI= IE1E2I= IE1IIEzl~ IE1'IIEzl= IE'I or lEI= IE1Ezl= IE1I IEzl!;; IE liiEz'l = IE'I is obtained.

®E =Elo(VaEr); LetE1' E 8*(E1). Then, by the induction hypothesis, IE1I~ IE1'I holds. Hence by (6), lEI= IE1ol= IEdociE1'Io= IE'I is obtained. This completes the proof.O

Now, using the operator 8 defined above, we obtain an algorithm for the inductive inference problem of context-free languages, which is quite simple and based on the principle of "identification by enumeration".

Definition 3.1 (admissible presentation [Laird 1986])

(i) Let do be a context-free language of target. An oracle EX is called complete and sufficient for do if there exists a signed subset K of Q satisfying the following :

(1) the set {EE 01 for all e in K, if e is positive, then lei~ lEI, else lei~ lEI} is exactly the set {EEOIIEI = do},

(2) for every e E K such that lel~do, EX() eventually returns "+ e" at least once, and for every e E K such that lelq;do, EX() eventually returns" -e" at least once.

(ii) A presentation of examples of do is admissible if it has an oracl~ EX which is complete and sufficient for do.

Note. There ex1sts such a K for our case, that is, if we take K as the set {EE_n 11~1 is a singleton , and if it is in do, then E has a sign +, otherw1se 1t has a sign - }, then K satisfies the conditions mentioned above. Hence, we may assume the existence of the

admissible presentation of d0.

Before presenting an algorithm, we need some preliminaries.

, For a given target context-free language L, let 'I ={at, ... ,an} be the alphabet over which Lis defined. Further, for each k <;::; 1, let rk =TU.ikUd'kU{I}>,+,(,)}, where dk ={at, 02, ... , Ok}, d'k ={at, 02, ... , ok}.

For a given expression E and i ~ O, k~1. let 8(E,i,k) ={E'IE-iE' and E' is a string over rk}. Then, 8*(E)= Ui ~oUb:t8(E,i,k). We abbreviate 8(1}>,i ,k) as 8(i,k). The algorithm requires an enumeration procedure which, starting with 4>, enumerates every expression in 8*(E).

As a notation, we denote an element of 8(i,k) by [E,(i,k)]. Note that for each i,k, 8(i,k) is finite. Further, let 8(i + 1,k) = {E'IE-E' and EE8(i,k), E'Erk*}, that is, an element ?f 8(i + 1 ,k) is obtained from an element of 8(i,k) by applymg 8k once, where 8k is a restriction of 8 to rk. Each 8(1,k) is obtained from 4> by one application of 8k.

[The outline of the algorithm]

Now, the algorithm works as follows: By applying 8k to 4>, it enumerates a hypothesis (an expression) E and stores into a queue Q in the form of [E,(i,k)]. then refines (generalizes) each hypothesis by examples. The enumeration is performed in the order as in

8(1,1), 8(2,1), 8(1,2), 8(3,1), 8(2,2), 8(1,3), 8(4,1), .... That is, the algorithm dovetails the enumeration of 8(i,1),8(i,2),8(i,3),-.. with thatof8(1,k),8(2,k),8(3,k),-··.

For a hypothesisE, if it does not cover some positive example(it is called "too specific"), then the algorithm generalizes E in some way. Otherwise, ifits language lEI includes some negative example(it is called "too general"), then the algorithm simply discards it. This is repeated until a correct hypothesis is found.

The algorithm is given as Algorithm At.

For the sake of helping one understand the process of enumerating hypotheses in the algorithm, Figure 1 illustrates how the contents of a queue Q changes during the enumeration.(The contents of Q is represented as a rectangle whose length may change as the time goes. The shadow portion of Q denoting 8(1,k) is created only

!. :.\i~~~iih~· A:~· <1~£~·~~~~~ ·Ai~~~ith~ ·£~·~ ·c~~~~t~i;~~ · L~~~~~~~~i · · · :Input: A recursively enumerable set of context-free . expressions n . An enumeration operator 6 : An admissible presentation of a target language do :Output: A sequence of expressions E1, E2, ... such that En is : correct for the first n examples. :Procedure: ! Q<-8(1,t);{elements of6(1,t) are stored in the queue Q} j EXAMPLES+-<~~ (empty set) · X+-next(Q);{next removes the top element of Q} do (forever): EXAMPLES+-EXAMPLESUEXO {get next example} while (let X=[Ej,(i,k)) be thej-th elementof6(i,k) , then) 3e E EXAMPLES s. t. Ej is not correct for e if Ej is "too specific" then do if i li: 2 then if k=tandj=t then append 6(1,i)6(E1,t,t) to the tail of Q; X+-next(Q); else append 6(Ej,t,k) to the tail ofQ; X+-next(Q); else append 6(Ej, t ,k) to the tail of Q; X+-next(Q); else (Ej is "too general") discard Ej ; X+-next(Q); Output Ej as the next hypothesis. i where E is "too specific" : = if 3+eEEXAMPLES s.t. ef lEI , then return true else return false E is "too general" : = if 3-eEEXAMPLES s.t. e EIEI, then return true . else return false ................... ..................................................................... .. .......... .....

when 8(k + 1,1) is produced from 8(k,1), and it is placed before 8(k + 1,1)).

Theorem3.1

For any given context-free language do, the algorithm At identifies do in the limit.

Proof. We need to show the following two: First , the algorithm At converges some hypothesisE, secondly, the hypothesis E is correct for the target do.

From the completeness property of 8 ((i) of Lemma 3.1) and Theorem 2.2, there is a chain of generalization steps from 4>: I}>=Eo-Et---·-En=E and IEI=do. Here we assume that n is as small as possible for the given do. Property (ii) of Lemma 3.1 together with the minimality ofn ensures that for each i, lEi I ciEnl· Then, there are strings Wi such that Wi E lEI and Wi flEd. Let En be in 8(n,k).

[Proof for correctness] Assume the algorithm converges to some expression E: that is , there exist i,k time

~0 and E in 8(i,k) such that E is correct for not only all examples in EXAMPLES but also every example given in the future. (That is the definition of "convergence".) Hence, E is correct for do.

[Proof for convergence] Suppose that the algorithm diverges. Then, we show, by the induction on j , that every hypothesis Ej (O ;;>j ;;> n)in the chain above appears on the top of Q and is generalized. When j=O, it is trivial. Suppose that Ei appears on the top of Q as a hypothesis in 8(i,p) and is generalized. Since Ei+ 1 E8(Ei), Ei + 1 E8(i + 1,q) for some q. The divergence of the algorithm implies that the finite number of expressions preceding Ei + 1 will all appear on the top and be generalized or simply discarded. Hence, Ei + 1 eventually appears on the top of Q and is generalized due to Wi+1· Thus, En(j=n) eventually appears on the top. However, because of the assumption of the divergence, En is not correct for some w, which contradicts the fact that IEnl=do. Hence, the algorithm converges.

Thus, we conclude that the algorithm converges to a correct expression.D

3.2 Inferring Semilinear Languages

If we restrict our attention to a subclass of context­ free languages called semilinear languages([Gruska 1971]), then we can easily get an operator for enumerating all expressions over T2, where T2 =Tu{cr1,cr2}, and obtain more efficient and simpler inference algorithm for the class. This is due to the fact that Any semilinear language over T is contained in 0T 2 , that is , for any semilinear language L over T there exists a context-free expression E over T2 such that L=IEI holds.(Note that the rules (1)-(4) in 8 form a context-free grammar, provided that r is finite.)

As a natural conclusion, we have:

Theorem3.2

There exists a simple algorithm for inferring semilinear languages in which the ·enumerator 8 ts achieved by a context-free grammar.

Proof.(Similar to that ofTheorem 3.1 and omitted.)O

4. Meta Inference

As we have mentioned, an expression enumerator 8 for semilinear case is realized as a context-free grammar, which implies that an enumerator in the liD is identified with a context-free expression. Therefore, one can think of a meta inference problem in which for a given target, the meta-liD infers a representation (context-free expression, or enumerator) denoting the target from examples of expressions, where the target is a class of expressions (or, a class of semilinear languages denoted by the expressions). Note that since the input of meta-liD, which is an expression, can be regarded as a string over some alphabet, the inference schema of the meta-inference problem is structurally equivalent to that of the inference problem in the usual sense, which is illustrated by Figure 2 . ·

,,

ACKNOWLEDGEMENTS

The author is grateful to Dr. T. Kitagawa, the president of liAS-SIS, for ceaseless encouragements. He is also indebted to Dr. H.Enomoto, the director of liAS-SIS, for providing useful reference papers as well as invaluable advice. Last but not least, discussion with the colleagues Y.Takada, Y.Sakakibara, and H. Ishizaka was very fruitful.

This work is a part of the major research and development of FGCS Project conducted under the program setup by MITI.