Context Free Grammar Identification from Positive Samples

  • Abstract
  • Keywords
  • References
  • PDF
  • Abstract

    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.



  • Keywords

    CFG, Identification in the Limit, Chomsky Normal form, Parse tree, Grammatical Inference, Pumping Lemma

  • 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




Article ID: 17768
DOI: 10.14419/ijet.v7i3.12.17768

Copyright © 2012-2015 Science Publishing Corporation Inc. All rights reserved.