Context Free Grammar Identification from Positive Samples
Keywords:CFG, Identification in the Limit, Chomsky Normal form, Parse tree, Grammatical Inference, Pumping Lemma
In grammatical inference one aims to find underlying grammar or automaton which explains the target language in some way. Context free grammar which represents type 2 grammar in Chomsky hierarchy has many applications in Formal Language Theory, pattern recognition, Speech recognition, Machine learning , Compiler design and Genetic engineering etc. Identification of unknown Context Free grammar of the target language from positive examples is an extensive area in Grammatical Inference/ Grammar induction. In this paper we propose a novel method which finds the equivalent Chomsky Normal form.
 N. Chomsky, â€œOn certain formal properties of grammars,â€ Information and Control, 2(2) (1959), pp.137â€“167. doi:10.1016/S0019-9958(59)90362-6.
 C. la Higuera, â€œA bibliographical study of grammatical inferenceâ€, Pattern 270 Recognition, 38(9) (2005), pp.1332â€“1348.
 Y. Sakakibara, â€œRecent advances of grammatical inference,â€Theoretical Computer Science ,185 (1997), pp.15â€“45.
 E. M. Gold,â€œLanguage identification in the limit,â€ Information and Control ,10 (1967) ,pp.447â€“474.
 D. Angluin, â€œQueries and concept learning,â€ Machine Learning 2 ,(1988) ,pp.319â€“ 342
 L. Valiant, â€œA theory of the learnable, â€œCommunications of the ACM, 27 (1984) ,pp.1134â€“1142.
 D. Angluin, â€œInductive inference of formal languages from positive data,â€ Information and Control 45(2) ,(1980) ,pp.117â€“135.
 D. Angluin, â€œInference of reversible languages,â€ Journal of the ACM 29(3) ,(1982),pp. 741â€“765.
 E. M. Gold, â€œComplexity of automaton identification from given data,â€ Information and Control 37(3), (1978) ,pp.302â€“320.
 J. E. Hopcroft, J. D. Ullman, R. Motwani, â€œIntroduction to Automata Theory, Languages, and Computation,â€ 3rd Edition, Pearson, 2006.
 Tai-Hung Chen,Chun-Han Tseng,Chia-Ping Chen,â€Automatic learning of Context free grammars,â€ROCLING 2006
 John C. Kieffer and En-hui Yang, â€œDesign of context-free grammars for lossless data compression,â€ Proceedings of the 1998 IEEE Information Theory Workshop, pp. 84- 85.
 H. Ney, â€œDynamic Programming Speech Recognition Using a Context-Free Grammar,â€ Proceedings of ICASSPâ€™87, pp. 69-72.
 Alexander Clark,â€Learning deterministic context free grammars: The Omphalos competition,â€Mach Learn (2007), pp.66:93â€“110 DOI 10.1007/s10994-006-9592-9.
 Yasubumi Sakakibara,â€œLearning of Context free grammars from Structural data in polynomial time,â€ Theoretical Computer Science ,76 (1990),pp. 223-242
View Full Article:
How to Cite
LicenseAuthors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under aÂ Creative Commons Attribution Licensethat allows others to share the work with an acknowledgement of the work''s authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal''s published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (SeeÂ The Effect of Open Access).