Context Free Grammar Identification from Positive Samples
DOI:
https://doi.org/10.14419/ijet.v7i3.12.17768Keywords:
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
Downloads
How to Cite
Received date: August 18, 2018
Accepted date: August 18, 2018
Published date: July 20, 2018