Context Free Grammar Identification from Positive Samples
DOI:
https://doi.org/10.14419/ijet.v7i3.12.17768Published:
2018-07-20Keywords:
CFG, Identification in the Limit, Chomsky Normal form, Parse tree, Grammatical Inference, Pumping LemmaAbstract
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.
References
[1] 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.
[2] C. la Higuera, “A bibliographical study of grammatical inferenceâ€, Pattern 270 Recognition, 38(9) (2005), pp.1332–1348.
[3] Y. Sakakibara, “Recent advances of grammatical inference,â€Theoretical Computer Science ,185 (1997), pp.15–45.
[4] E. M. Gold,“Language identification in the limit,†Information and Control ,10 (1967) ,pp.447–474.
[5] D. Angluin, “Queries and concept learning,†Machine Learning 2 ,(1988) ,pp.319– 342
[6] L. Valiant, “A theory of the learnable, “Communications of the ACM, 27 (1984) ,pp.1134–1142.
[7] D. Angluin, “Inductive inference of formal languages from positive data,†Information and Control 45(2) ,(1980) ,pp.117–135.
[8] D. Angluin, “Inference of reversible languages,†Journal of the ACM 29(3) ,(1982),pp. 741–765.
[9] E. M. Gold, “Complexity of automaton identification from given data,†Information and Control 37(3), (1978) ,pp.302–320.
[10] J. E. Hopcroft, J. D. Ullman, R. Motwani, “Introduction to Automata Theory, Languages, and Computation,†3rd Edition, Pearson, 2006.
[11] Tai-Hung Chen,Chun-Han Tseng,Chia-Ping Chen,â€Automatic learning of Context free grammars,â€ROCLING 2006
[12] 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.
[13] H. Ney, “Dynamic Programming Speech Recognition Using a Context-Free Grammar,†Proceedings of ICASSP’87, pp. 69-72.
[14] Alexander Clark,â€Learning deterministic context free grammars: The Omphalos competition,â€Mach Learn (2007), pp.66:93–110 DOI 10.1007/s10994-006-9592-9.
[15] 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
License
Authors 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).
Accepted 2018-08-18
Published 2018-07-20