Grammatical Inference on the Basis of Linear Environments of Symbol Strings

1. INTRODUCTION

Grammatical inference is a problem of inferring a grammar which describes a language by means of a finite set of sample sentences of the language. According to the development of formal linguistics, grammatical inference has recently received increasing attention as one of the most important information-processing problems. It serves as a tool for automatic acquisition of many sorts of grammatical descriptions which are dealt with in pattern recognition, graph theory, programming language design, information retrieval and other parts of artificial intelligence study.

We propose here a practical, systematic grammatical inference procedure. It has the following properties. (1) The procedure can be applied to languages which are impossible of desciption by any regular grammar. (2) The procedure does not need any structural information of sample sentences. (3) The procedure works without feedback by teachers. (4) The procedure is efficient, i.e., enumaration of grammars is not employed.

In many effective methods of grammatical inference, production rules are often inferred on the basis of some supposed relationship between similar parts of sample sentences. We use a notion of "bounded context" .which represents linear environment of a symbol string in sample sentences, and define an equivalence relation of strings by equality of the bounded context.

The next simple example explains our method. Suppose sample sentences are the strings

ab, aabb, aaabbb, . . . .

The two substrings 'ab' and 'aabb' appear in the same environment in the sentences, because they are put in the places denoted by [ 1 in the following [ 1, a[ 1b, aa[ 1bb, ·.. ~This means the two substrings are context-equivalent. Grammars are constructed from production rules which consist of pairs of context-equivalent strings and from reduced sample sentences. Here the production rule ab~aabb is inferred on the basis of the context equivalence. The reduction of sample sentences is carried into effect by replacing all 'aabb' in them by 'ab' repeatedly until no 'aabb' exists. Then all of the sample sentences are reduced to a single sentence 'ab'. We call it a reduced sample sentence. The inferred grammar is described by the triplet ({a,b},{ab~aabb}, {ab}). This description of grammar is a little different from that of ordinary formal grammars, but obviously grammars of this type can be transformed into ordinary context-sensitive grammars.

2. FUNDAMENTAL DEFINITIONS

We establish the basic concepts necessary for the expression of our procedure. First, the preliminary notations are provided. An alphabet is denoted byE, and we use a, b, c, ... as symbols. Symbol strings are denoted by u, v, ... , z except the empty string A. A set AB consists of concatenation strings of elements of A and B. The notation A* is the closure for A. A language is a set of strings and denoted by L, L', etc. We call an element of a language a sentence. The length of a string xis denoted by lxl.

DEFINITION 2.1. The kt-bounded context of a string w in a language L is a set of pairs of strings

C~t(w) = {(lastk(x),firstt(y))}l xwy £ L} ,

where the parameters k,~ are non-negative integers or infinity and firstk(y) (lastk(y) ) is y's leftmost(rightmost) substring of Iength k, if lwl < k, otherwise w. The context equivalence kt kt ~L is defined as follows: w ~ 1 w' if and only if c~t(w) c~t(w') .

DEFINITION 2.2. A symbol substitution grammar is a triplet G = (L, P, S), where Lis an alphabet, P is a set of production rules which are of the form x+y and S is a finite set of strings called an initial set of sentences. In correspondence with ordinary formal grammars, we call it a type-1 ssg if x is not longer than y for any x, y in x+y £ P. The language L(G) generated by a grammar G=(L,P,S) is the set of strings generated from S by P, denoted by gp(S). More precisely, gp(S) is defined by

* where the relation of strings v ?u means that v = u or there is a sequence of strings vo,···, vn such that v = vo? ... fvn = u while v fv' denotes that there exist x, y, w, w' which satisfy v = xwy, v'= xw'y, w + w' £ P.

Our procedure infers grammars of this type.

3. GRAMMATICAL INFERENCE PROCEDURE

Before presenting our procedure, we need some preliminaries. An order relation · of strings is defined as follows: i) x · y, if x is shorter than y, and ii ) two strings of the same length follows the lexicographic order. The j-th non­ empty string in the order is denoted by z(j).

-1 Next we define an operator gp which is a mapping from the set of strings to itself. Intuitively, g; 1 (w) is the reduced sample sentence of w.

DEFINITION 3.2. Let a set of production rules P be {x +y I m=l,···,j} . The reduced string of w, m m _ 1 denoted by g (w), is the string obtained by applying thepproduction rules in P tow in such a manner that any ym in w is replaced by xm r epeat.edly, until no ym remains in w. The operator can be applied to a set of strings.

Our grammatical inference procedure produces grammars by receiving as input a finite number of positive sample sentences. The system includes two arbitrary parameters: an order relation · of symbols, and a pair (k,t) of non­ negative integers and/or infinities. The system outputs an ssg defined above. It is also type-1 because of the way of making production rules in the procedure.The procedure is described in the ALGOL-like form as follows:

S:=L'; P:=<j>; jj:=l; for i := 1 step 1 until oo do begin for j :· jj step 1 until oo do begin if lz(j) I < maxlwl then go to OUT kt W£:::i if c 5 (z(j)) + <P then end; for m := 1 step 1 until j-1 do H if z(j) ~ 1 , z(m) then begin P := {z(m)+z(j)} UP; S ;a g; 1 (L') go to NEXTSTRING end NEXTSTRING: jj := j+l end; out: print( (L, P, S) )

In the procedure, L' is the set of sample sentences, and S is the set of (partially) reduced sentences. The strings z(j) (jal,2,···) are tested in order: I) If z(j) is longer than any string in S, the grammar is output, since no more rules can be found. II ) Otherwise it is tested for every string z(m) shorter than z(j) whether or not z(j) is context-equivalent to z(m). If it is true, . the procedure adds a production rule z(m)+z(j) to P, and recalculates S reducing the sample sentences L' by the new P.

EXANPLE 3.1. Let sample sentences be ab, aabb, aaabbb, abc, abcc, abccc, abcccc, aabbc, aabbcc. Hhen we choose parameters (1,1) and · such that a·b·c, a type-1 ssg

G 1 l·(L') = ({a,b,c},{c+cc,ab+aabb},{ab,abc}) - ' is inferred. This grammar describes a language L(G 1 l·(L')) = {aibicj I i~l, j~O} - '

Table 1 shows the process of obtaining the ssg.

4. PROPERTY OF INFERRED GRAMMARS

We describe property of grammars inferred by our procedure and possibility of correct inference. There have been found the following facts: i)Inferred grammars are consistent with the sample sentences. Precisely, sample sentences are grammatically correct with respect to the grammar obtained from the sentences, that is, the language described by the grammar includes the set of sample sentences.

:li) The grammar inferred from sufficiently many sample sentences describes correctly the source language of the sample sentences. Precisely, if a source JJlnguage L satisfies a condition, which we call "' -inferability, then the language is inferred correctly from any complete sequence of L's sample sets by the use of any kt-bounded context in which k and tare sufficiently large integers. A sequence of sets of sample sentences from a language L is complete iff for any w in L there exists a positive integer t such that for all t'>t L~, incl~es w.

~) The class of "' -inferable languages includes all of regular languages and many non­ trivial context-free languages.

When the procedure in which non-bounded context is used produces a grammar, we call the input language is~-inferable. We also let source languages which are usually infinite sets be input, by giving an algorithm to calculate any description of bounded context.

EXAMPLE 4.1. Let us consider the following

seguence of sample sets from a language L = {a bn I n~l} : L 1 ={ab}, L 2 ={ab,aabb},···, LN·{ab, · · · ,aNbN}, · · · . For example, by using 4,4-bounded context, we get the sequence of grammars: G 1 ,G 2 ,··,G 5 ,···, where �N=(E,~,LN), (N·l,···,5) and G 6 =G 7 =···=(E,{ab+aabb},{ab}). We

must notice that the grammar G 6 =G 7 =··· describes the source language L correctly.

EXAMPLE 4.2. The following table makes us under­ stand that most of inferred grammars are not so redundant and may reflect properties of their source languages. They are similar to the cfg's we may think of from the source language. These grammars can be inferred from any sample sets which includes all strings longer than a costant length.

5. DISCUSSION

We implemented the procedure, which was written in LISP, and tested real sample data (simple sentences of natural languageE and feature sequences of letter patterns). The processing of the data helped us to recognize the following ideas: i) It is important to s~lett good parameters k, t in accordance with the application. We need too many sample sentences to obtain correct grammars, if k, t are very large. ii ) It may be interesting to change the parameters dynamically by observing the convergence of inferred grammars. ~) If noise is expected, we had better employ 'similarity' instead of equivalence. iv) Quick parser can be constructed, which may be simpler than that of cfg. It seems able to be deterministic, or not needed backtracking.

ACKNOWLEDGMENTS

The auther is grateful to Dr. S. Amari of Univ. of Tokyo for many helpful suggestions.