Reduction of Enumeration in Grammar Acquisition

1. INTRODUCTION

An acquisition theory for language must contain according to Chorr.sky (1):

(i) an enumeration of the class {y.}of possible sentences; 1

(ii) an enumeration of the class {s.}of

a way of evaluating and selecting possible alternative grammars.

possible structural descriptions; 1 (iii) an enumeration of the class {G. }of possible grammars; J (iv) specification of a function (i,j)·f wh ich specifies the structure sf assi­ gned by any grammar G. to any sentences y.; ] (~)

A model for language acquisition at tempts to model language learning, or mo­ re precisely the learning of linguistic "competence". In a very abstract version, the model is an algorithm which works on certain primary linguistic data, and pro­ duces a grammar.

This paper presents a model for langua ge acquisition which operates on the fol~ lowing primary data:

a) a finite sample of sentences, and

b) their structural descriptions;

c) non-sentences identified as such.

We note that the availability of struc ture (item b)) differentiates this model­ from other current studies on the acquisi tion of grammar (2) (3). -

The knowledge of structure, prior to

• Work supported by Consiglio Nazionale delle Ricerche .
• ·· The first part of this study was done in the Dept.of Computer Science, Uni­ versity of California, Los Angeles.

the acquisition of a grammar, ca n be de­ fended on three grounds. First a child learning a language has stress and intona tion information available to him and - this could be interpreted as a ty;e of structural information. Second, if our grammars describe the base component(deep structure) of a language, then there is an intimate relation between structure and meaning, the structure being a prere quisite for understanding a sentence. The widespread belief the there must be a par tially semantic basis for the acquisition of syntax then implies the availability of some structural information to t b e learner of the language. Third availa bility of structure greatly red~ces the number of alternative possible grammars . . . and 1nsures that the acqu1red grammar ge nerates sentences wit h structures consi~ stent with their meanings.

Given the data, a model could consider the enumeration (iii) of attainable gram­ mars, and test their compatibility with the data a), b) and c). The test is possi ble because of (iv). -

The model then selects one of the com­ patible grammars by means of the evalua­ tion measure (v). A more accurate model should also explain the gradual develop­ ment of an appropriate hypothesis, and the continual accretion of linguistic com petence, rather than just considering the idealized instantaneous moment of acquisi tion of the correct grammar. -

~e note with Chomsky that different e­ valuation measures will assign different ranks to alternative hypotheses regarding the language of which the primary data are a sample. Hence choice of an evalua­ tion measure for grammars amounts to de­ ciding which generalizations about lan­ guage are significant.

The class of possible hypotheses must be limited, if a realistic theory of syn tax acquisition is to be developed. How~ ever, the limitation must still yield a class of grammars that is adequate in strong (and a fortiori weak) generative capacity. But beyond this, the require­ ment of feasibility is the major con­ straint of the model.

I shall have very few words to add to Chomsky's formulation of the problem, mainly for carrying further the formali­ zation. My concern was for (1) delimiting a class of grammars which proved adequate in strong generative capacity, and defin ing a strategy for (2) reduction of pos~ sible hypotheses, and for (3) selecting a unique grammar. There is some similari ty between the grammars that we are going to describe, and Bar-Hillel's (4) catego rial gr ammars. -

A model similar to the one that we s hall describe - although of reduced sco pe - proved its feasibilit y on the compu ter (5)(6). -

Following Gold (7), Feldman (2), Cre­ spi -Reghizz i (5)(6) and Biermann (3),con sider a context-free source rammar GS - and a source language LS = L(GS . _

The parenthesis grammar G I is de rived from G = (VN,VT,P,S) by reptacement of every productio~ A·u, u in V - V~ , wne re , V = VN U VT ' wlth the parenthes1zed product ion A -+[u] , where "[" and "]' are not in ~T · ~~ote t hat "renaming produc­ tions" 1.e. productions such as A·B ,where B is a nonterminal , are not parenthesized.

!:.!.~m p 1 e

Gl: S·P.S IHa

H·bP.Ia

[Gl] : S·~)s] I [Ha]

1!-+[bH] [a J A structura l information sequence ISof language ~S is the ordered set:

IS= f s 1 ,s, ... ) where so is in L([Gs]>, and every ~ent ence of the Iatter language occurs sooner or later, perhaps with rep~ titian , in L .

~e note t~at IS provides items a) and t) of the primary ddta. The information sequence could start wit h the strings: Il = i [ [a] a],[ [b[b[aJ J J a] ,

[ [a= [a] [ [a] a J J J ,

.. lterna tively, we shall write [[a]a] as a a .

Si;:;ilarly , we introd 'JCe a roegati ve in ­ fcr':1at ion se quence :rs de fined as an enume raci er. of all the non-sentences:

Ns ={ nl,n2, ... } v P = v Tu { [. ]l 0 where n is in v· L i p - s.

A positive sample St ={s 1 ,s 2 , ··. ,st}

and a negative sample M = { n ,n , ... ,n } compose the primary datA avaitabfe to the model at the discrete time t. At each time t we are interested in ouserving the gram mar G which is output by the grammar ac~ quisition device to account for the sam­ ple S and M · G must meet two require­ mentstfor co~patibility with the data: 1) L( [Gtj);?St 2) L([Gt)nMt =~

If the model has to account for the in creasing linguistic skill of the learner­ we have to cons~der t~e g~ammars Gtl'Gt 2 ' ... , at success1ve tlme 1nstants

t 1 ,t 2 , ... corresponding to samples

Stl , St 2 · ·.,. We shall expect the gues­ ses of the algorithm to become closer to the source language, as the sample is en­ larged.

The model is said to identify the sour­ ce grammar G 5 in the limit if there is a time t' such that for t >t 1 , a nd for any information sequences IS , NS : 3) G : G t t' 4) L([Gt]) = L([G 5 J>.

In other words, identification in the limit implies that there are primary data S , M , t>t', which cause the model to se l~ct ~ grammar which is not later changed and is strongly equivalent to the source grammar. This must be true for any infor­ mation sequences for that source grammar.

Two results, due to Gold (7), should be me ntioned.

Theorem 1 - Let C be a class of decidable grammaxos (i.e. grammars for which it is decidable whether a string is generat ed by the grammar). Then, if GS is in C there is an algorit hm which identi­ fies G in the limit.

Theore~ 2 - Let C be a class of gr ammars which generate all the finite languages and any one infinite language. Assume the primary data consist only of a positive informati on sequence. Then, if Gs is in C there exists no algorithm for t~e class C which is able to identify GS in the limit.

As a special case of 7heorem 1, context free languages are identifiable in t he li mit, if sentences and non-sentences (iden tified as such) are given. If the latter­ are not available, Theorem 2 implies that not even finite state languages can be identified in the limit.

~e note that the proof of the first theorem is based on the fact that gramma~ are enumerable, and on t he possibility of testing 1) and 2) f o r a dec i dabl e gr~mmar. Such a proof does not lend itself to a feasi=le grammar acqu isi tion method for context-free grammars, because of the astronomical number of grammars to be te sted.

2. A CHARACTERIZATION OF POSSIBLE GRAM­ HARS

In a previous work (5)(6) we have in­ troduced a subclass of context-free gram mars, termed free operator precedence - grammars, for which identification in the limit is possible when only positive in­ formation is available . In this sequel we discuss an extension of these concepts,to include more ~eneral classes of language~

We shall first define a fa~ily of clas ses of gram~ars(k-distinct grammars)which cover the entire spectrum of context-free languages.

When a further restriction on the form of productions is imposed we obtain the family of k-distinct and k-homogeneous grammars, whose strong generative capaci ty does not cover the full spectrum of - context-free languages,although our new grammars are able to account for self-em bedding, nesting and other features re-­ quired for natural languages.

For each class of grammars in the fami ly,identification in the limit - without­ knowledge of non-sentences - is theoreti cally possible and practically feasible~

We now introduce some new definitions. Let G = (VN,VI,P,S) be a context-free grammar, and et Vp = VTU {[,]}.

Define the left prof~le of order k of a string x in v+ as:

y in v ; , $ is not in V p}

Similarly, the right profile of order k of a string x is:

: VU, X

in

Example :

For the previous Gl we have

The k-profile of a nonterminal A is de fined as:

8) Pk(A) : (~ Lk(xi) union is performed for A~xi in the production ~ Rk(xi)),where the every production set.

A gramnar is k-distinct iff, for any two nonterminals A, P: Pk(A) = Pk(E) implies A = B.

Example:

Gl is 1-distinct since :

It is obvious that if a grammar is k­ distinct, it is also m-distinct, for an y m> k.

Let G ~ (VN,VT,P,&), and suppose that for A, B 1n VN:

Vp }: T 2 · In this case we say that G has no dupl~cated product ions. It would be easy to prove that every c.f. grammar has a strongly equivalent grammar with no du­ plicated productions and we can restrict our attention to non duplicated grammars without loss of generality.

Next we prove that any context-free grammar with no duplicated productions is k-distinct for some k>O.

Theorem 3 - G is k-distinct for some k>O.

Proof - Let u be the shortest string whic h is in TA but not in TB' and let j = u +1. Then uf is in L.(x.), for sor.:e A-+x. in p; Since u$ is notJin~ L.(y.) for any ~ther production B-+y., it f6116ws that P.(A) r P.(B). In the §arne way determine J j for arty pair A, B in VN, and let k be the lara est of the inteJers thus determined. Then G is k-distinct .

Non-terminals of a k-distinct grammar are uniquely characterized by their k-pro files, which can be used as standard na-­ ~ for nonterminal characters.

Example:

Gl is 1-di~tinct and can be rewritten as follows· :

• For the sake of readibility Pk(A) as < ... ; ... > we write

I ~ is obv i ous ~ h a~ ~he se~ of non~ermi na l names f or an y k-dis~inc~ grammar of f ini ~e ~erm i n al vocabulary is fini~e. I~ follows ~ha~

Th eo rem 4 - The class of k-dis~inc~ grammars wi~h s~andard non~ermi­ na l names and wi~h righ~ par~s of bounded l e ng~h, over a fi n i~e ~erminal alphabe~ VT' i s f in i~e .

Proof - f o r a ny produc~ i on A· x we have --- lxl ~n, for some n> O. Bu~ ~here a r e f i ni~e ly man y stri n~ s of lenf,t h n~l over ~h e f i n i ~e se~ VPU 1 se~ of non"termi na !s o f a k- d istinct era ~nar }

3. f... GRA:.l :iAR ACQw i SI 7I :):; ALGOREE:!

7~e algorithm t o ~e ~e scr i ~e d is able to id e n ~if y in ~he l i mi t a subclass of k­ di s ~in c~ grammars, whi c h we will define a f ~ er p resen~ i ng ~he a l gori~hm.

Con sid er a sampleS of L 5 , and le"t s=a 1 a 2 ... a n be a s~rlng of St. Enclose s b e ~ wee n special delimi "ters a = J. and a 1 = ~ . Th e algori~hm is soge how simi­ l~ t- t o a s yn ~ax analyzer, and makes use of a pu s hdow n s~ack where all scanned sym bol s are copi ed and renamed Q 0 1 ... Q. ~ Provision s f o r d e~ec~ i ng erro?s ln ~he 1 s t ri ~g s ( e. ~ . non-balancing bracke"ts)ceuld be easily added.

Cc~m e n ~ a l gori~ h m for ~he cons~ruc~ion of a--k - d is t inc~ grammar from a s"tring s;

Q 0 : = a 0 ; i := 0 ; h : = 1 ;

Ll: if a h ;. ".1." ~ h e n

begin i : = : = i ~ 1

if Qi = "]' ~

L2:begin j : = j - 1;

i f Q j

;. " [" ~ h e n .i::. .!2. L 2 ;

Qj : = pk ( Q j~l · ... 0 i-l) ;

C rea~e ~ h e produ c~i o n "<pk( Q j~l···

·· Q. 1) > · Q. 1" ·· Q. 1";

i

l- J ~

: = j ~ ~ o Ll

end e l se ~ ~o Ll ;

l -

end

c ~ e a t e t he produc~ion 'S·Qi';

It is bes~ seen f rom an example ~ha~ t he gr a mmar G. co n stru c ~ed by ~he algori­ t hm from ~ h e §~rings. is comp a~ible wi~h s 1 . , i. e., s . is in Ltrc .J>. l ~ l Lxa.npl. e

Applying t he algorit hm ~o s 1 =!a, we de riv e t he 1- d istinc~ grammar G 1 :---

In te rm e d ia~e

s t e ps

[[a] a]

L <a ; a>. a]

s

<a a> ... a a>

<a a>a

s

<[

a>

or in a more readable form

In order ~o comple~e ~he grammar ac ­ quisi~ion process, ~he algori~hm is ~hen applied ~o ~he sen~ences s 1 ,s 2 , ··· ,s of ~he sample 5 , yielding ~he grammars~� 1 , G 2 , ··· ,�~. :r~x~ ~he union is performed :

. : : o~e ~ha~ ~he grammars G 1 , G 2 , ··· , � ~ have non-disjoin~ nont erminal vocabula­ ries.

Consider t h e sample 5 3 ={ ! a, b b !~ ! ! ! a} from ~he grammar c 1 .

Carrying on ~he example, from t h e se­ cond sen~ence 5 2 = b baa we derive c 2 :

G 2 : <a a>· a

<b J >·b<a ; a>

<b J >·b<b ;]>

<[ a>·<b ;]> a

ve G3 :

5 . <[ ; a>

and, finally, from = ! !

G .

3 .

<a a> · a

<[; a>· <a ; a>a

<[;]>·<a ; a><[; a >

<[;]-<a ; a><[;]>

5 . <[;]>

A · a

c

bA

c · bC

B · Ca

5 B

! a we deri

A . a

B A a

D AB

D AD

5 D

The union G I = G 1 U 3 G2 U G3 is :

G I

3

A

B ·

c

D

5

a

Aal ca

bAibC

AB IAD

B I D

Examining G) we see ~hat � ~ is c om~ati ble wi~h 5 3 , bu~ that L<Cc 3 ] ) c: L(LGl]> since for ins~ance b ! ! ! a i s not ge-

nerated by G)· Consider i ng now a larger sample

5 5 = 5 3 vf~ ~, ve ~he grammar c5 as b a a a} , we deri-----

Gl 5

A ·

B

c

D

5

a

Aalca

bA i bC

AfiiADics lc D

BID

This grammar is s~ronel y equi valen~ ~o Gl,

53

and ~he grammar acquisi~ion procedure is 1:hus comple't:ed.

Any grammar produced by 'the preceding algori't:hm is k-dis~inc't:, and, in addi1:ion has 1:he following proper't:ies:

(1) There are no renaming rules, excep't: for s~A, A in VN;

(2) for any 't:WO al~erna~ives A~x, A~y,whe reA is in VN- S, pk(x) = pk(y). -

Defini't:ion : a grammar having proper~ies (1) and (2) is called k - homogeneous .

Consequen't:ly, ~he hypo~heses space for 'this grammar acquisi~ion model consis't:s of 1:he class of k-dis~inc~ and k-homogeneous grammars ( shor't:ened 't:o k-d. h.). We already know from Theorem 3 't:ha~ any c.f. grammar has a s1:rongly equivalen't: k-dis't:inc't: form.

I't: would be easy to prove 'that any con­ 't:ext-free grammar admi1:s a k-homogeneous s't:rongly equivalen't: form. Wha't: is more re­ levan't: 1:0 our discussion is ~ha~ 'there are con't:ex"t:-free grammars which do no't: admit a s't:rongly equivalent k-d.h. grammar, i.e. a grammar 1:hat is simultaneously k-distinc't: and k-homogeneous. An example is provided by 1:he grammar G2

.:;2

S Ha

H ~ Sa I a

which genera1:es these~ {a 2 n l n = 1,2, .·. } wi't:h a leftlinear structure. G2 is 1-dis't:inc't: but no't: !-homogeneous, because p 1 ( Sa ) = ( { [ } ; {a } ) "I p 1 (a ) = ( {a } ; {a } ). Any a't:temp~ 1:0 render G2 !-homogeneous (by split't:ing H~sa l a into H ~sa, H ~a) will alter 1:he profiles in such ~ way 't:~at 'the new grammar is no longer 1-dis't:inct. The same can be shwon 1:0 be 'true for any order k of profiles.

On 1:he other hand we notice tha't: 'the sa me language is generated wi1:h a differen't: struc't:ure by 1: he 1-d. ~ . grammar G3 :

G3 :

S ~ aHiaK

H ~ a

K Sa

We do no't: know how 1:0 charac't:erize in general the languages wh ich cannot be str~ gly genera't:ed by k-d.h. grammars. from pre­ li~inary observations i't: seems 'that 'these­ languages are not 1:00 relevant to na't:ural (or programming)languages, as is 1:he case with {a2nln = 1,2, ... } , and tha't: res1:ric 1:ion of the hypothesis space 1:0 the class­ of k-d.h. languages is hopefully no't: 1:00 severe. An accurate examina1:ion of 1:his crucial point is the main targe't: of our f~ 't:Ure investigations.

Assume now that the so~rce language LS admits a k-d.h. grammar Gs. If 'the order k of the source grammar is known , 1:he algo rith~ will selec't: at any instant 't: jus't: one grammar out of 'the k-d.h. gram~ars which are compatible wiTh S . The selec1:ion of The grammar is perfor~ed by 1:he algori't:hm wi1:h a criterion which leads TO identifi­ ca't:ion in The limiT from a positive sam­ ple. The selected grammar generates The smalles't: language among the k-d.h. gram­ mars which are compa1:ible with 't:he sample.

Lemma 4 - LeT G :G(S )be 1:he k-d.h.gramm~ derived Ey 't:h~ algori't:hm from 'the sample S .Then There is no o't:her k-d.h. grammar 't: G' such Tha't:: S L([G ']l L([GT]l.

Proof : The productions of G are clearly ------ necessary for any k-d.h. grammar in order TO generaTe S · Therefore G' may differ from G only byTsome additional produc't:ions, 4nd iT follows 'that L([G'JP 2 L([G ]l.

Our ~ain result can now he proved.

Theorem 5 - LeT ST be a sample from a posi't:ive informa1:ion sequence Is, where L 5 is generated by a k-d.h . gra~ mar G . Le't: G be The k-d. h. grammar con­ STruc~ed by Tte algorithm from S . Then . T

thaT is the algoriThm identifies G 5 in 1:he limit ·

Proof LeT n be an upper bound on The leng't:h of any produc1:ion in G 5 · from 't:he facTs That 1) the class of k-d. h. grammars with productions of bounded length has finite cardinali't:y, and 2) G generates 1:he smallest language among t~e grammars of the previous class which are compatible wi't:h S , i't: follows that there is a Time 1:' and A sampleS' w~ic h causes 'the algorithm To derive a 't: gra~mar wh ic h is not later changed and is strongly equi valenT TO G · -

We noTe ~hat we are able to identify a language in The limit without knowled g e of a nega1:ive informaTion sequence. The paradox, with respecT ~o Gold's Theorem 2, comes from The fact that The class of k-d.h. grammars wiTh produc't:ions of bound ed length does noT generate all fi n ite - languages. --

We now discuss the case that the source language is k-d.h., but The order k is un known. In 1:his case we make use of nons en Tences, provided by a negative sample M ~ in order 1:0 discard the r,rammars produc~ d by the previous algorithm which are not compatible wiTh The nega1:ive sample. The algoriThm is The followinP-:

comment acquisiTion of a k-d.h. grammar for a source language of order k unknown. A posiTive sample S and a ne gaTive sample M are given; t L: k := 1 ; t

G : = k-d. h. grammar derived from S by pr~ vlous algorithm; ~

if L ( [ G ]l n M "i ~ Then t T

begin

k : = k + 1;

~ to L;

end;

In this case identification in the li­ mit is still possible but a negative in­ formation Ns is needed in order to deter mine the value of k which a priori is un­ known.

Example

The source language is defined by the grammar G4 :

It can be computed that L4 is a 2-d.h. language. Consider the positive sample 5 4 :

{a b

!!!!:::::!!!-. =.....- m - = a

=- a a b , a a b , a a a a b}

Assume k = 1, and derive a 1-d.h. gra~ mar from the four sentences of s 4 :

Suppose now ~ha~ a negative sample is gl ven : Ml = {~ ~} = {nl}

S . . . L ( [G ( ~ ) ]l , h . . 1 . 1nce n 1 1s 1n ~ t 1s 1mp 1es t hat a 1-d.h. hypothesis is not adequate. In other words �(~) . , which defines the smallest language in the 1-d.h. class, over-generalizes the sample s 4 .

Consequently, we consider the 2-d.h. grammar derived from 5 4 :

It can be verif~yd that n 1 = !_! is not generated by G ~ , which can be assumed as the current hypothesis. Actually, iden tification of G4 is not yet complete. If­ the positive sample were enlarged, the al gorithm would eventually derive a 2-d.h.­ grammar which is strongly equivalent to G4.

The last case to be discussed occurs when there is no integer k such that Gs is k-d.h.Then any attempt of identifying G 5 by means of our algorithm will fail.The current hypothesis of order k derived by the algorithm from any positive sample can always be falsified by 1uitable enlar gement of the negative sample against - which the grammar is tested.

3. CONCLUSION

If we compare our results with Chomsky's formulation of the problem of grammar acquisition, we see that we are far from a fully satisfactory solution, since the class of k-distinct, k-homoge­ neous grammars that we have considered does not cover the full spectrum of con­ text-free languages, much less that of Chomsky's transformational grammars.

On the positive side, the class of grammars for which we have provided a so­ lution does not seem less adequate than context-free grammars for modeling lin­ guistic competence, since self-embedding and nesting can be accounted for.

Our approach aimed at studying a learn ing situation where the language acquisi7 tion device uniquely determines a grammar from given primary data, which consist of a sample of sentences and structure de­ scriptions. Following this step, the gram mar can be tested for over-generalization against a set of non-sentences. If any non-sentence is accepted by the grammar, the learning device steps up a parameter which enlarges the class of attainable grammars, and determines a grammar in the enlarged class. The procedure always con­ verges to the source grammar, if the lat­ ter falls in the hypotheses space that we have already mentioned.

Perhaps the most significant result of this study is the definition of a suffi­ ciently limited - and still interesting - class of grammars, ar.d the use of pri­ mary data which include structure descri£ tions in order to reduce the number of grammars whic h , at a certain moment, are compatible with the available data.

A simple strategy selects an appropria te "minimal" grammar which can be extended, if necessary,as additional input sentences are added to the sample.

4. AKNOWLEDGEMENT

I am gratefull to Dr.ing. P. Della Vigna ~nd F. Schreiber for their valuable discussion of ~he problem. Many ~hanks are due ~o ~he reviewers of ~he manu­ scrip~ for ~heir many cri~icisms and su~ ges~ions.

5. REFERENCES

1. CHOMSKY, N., "Aspec~s of ~he theory of syn~ax", MIT Press, Cambridge, Mass., 1964.
2. FELDMAN, J.A., "Some decidabilhy re sul~s on gramma~ical inference and complexi~y", AI MEMO n. 89, S~anford Universi~y, S~anford, 1969.
3. (3} BIERMANN, A.W. and FELDMAN,J.A., "A. survey of resul~s in gramma~ical in­ ference", Proc. In~. Conf. on Fron­ ~iers in ;a~~ern recogni~ion, Hono­ lulu, Jan. 18-20,1971.
4. ( 4) BAR-HILLEL, Y., "Language and infor­ ma~ion", Addison-Wesley, Reading, Mass., 1964.
5. CRESPI-REGHIZZI, S., "The mechanical acquisi~ion of precedence grammars", Thesis, Universi~y of California, School of Engineering, Los Angeles, 1970.
6. (6} CRESPI-REGHIZZI, S., "An effec~ive model for grammar inference", Proc. IFIP Congress, Ljubljana, 1971-.----
7. GOLD, M., "Language iden~ifica~ion in ~he limi~", Infer. and con~rol, 10, 447-474, 1957.