Context Free Grammar Identification from Positive Samples

  • Authors

    • K Senthil Kumar
    • D Malathi
    2018-07-20
    https://doi.org/10.14419/ijet.v7i3.12.17768
  • 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.

     

     

  • References

    1. [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

    Senthil Kumar, K., & Malathi, D. (2018). Context Free Grammar Identification from Positive Samples. International Journal of Engineering & Technology, 7(3.12), 1096-1097. https://doi.org/10.14419/ijet.v7i3.12.17768