Context Free Grammar Identification from Positive Samples

  • Authors

    • K Senthil Kumar
    • D Malathi
    https://doi.org/10.14419/ijet.v7i3.12.17768

    Received date: August 18, 2018

    Accepted date: August 18, 2018

    Published date: July 20, 2018

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

  • 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.

  • 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

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