Improved Method for Learning Context-Free Grammar using Tabular representation (테이블 표현(Tabular representation)을 이용한 문맥자유 문법(Context-free grammar) 학습을 위한 개선된 방법)

SOON-HO JUNG (정순호)

doi:10.9708/jksci.2022.27.02.043

Improved Method for Learning Context-Free Grammar using Tabular representation

Journal of The Korea Society of Computer and Information
Abbr : JKSCI
2022, 27(2), pp.43-51
DOI : 10.9708/jksci.2022.27.02.043
Publisher : The Korean Society Of Computer And Information
Research Area : Engineering > Computer Science
Received : January 27, 2022
Accepted : February 23, 2022
Published : February 28, 2022

SOON-HO JUNG ¹

¹부경대학교

Accredited

ABSTRACT

In this paper, we suggest the method to improve the existing method leaning context-free grammar(CFG) using tabular representation(TBL) as a chromosome of genetic algorithm in grammatical inference and show the more efficient experimental result. We have two improvements. The first is to improve the formula to reflect the learning evaluation of positive and negative examples at the same time for the fitness function. The second is to classify partitions corresponding to TBLs generated from positive learning examples according to the size of the learning string, proceed with the evolution process by class, and adjust the composition ratio according to the success rate to apply the learning method linked to survival in the next generation. These improvements provide better efficiency than the existing method by solving the complexity and difficulty in the crossover and generalization steps between several individuals according to the size of the learning examples. We experiment with the languages proposed in the existing method, and the results show a rather fast generation rate that takes fewer generations to complete learning with the same success rate than the existing method. In the future, this method can be tried for extended CYK, and furthermore, it suggests the possibility of being applied to more complex parsing tables.

KEYWORDS

Tabular Representation, Context-free Grammar, Genetic Algorithm, Partitioning, Fitness

Citation status

* References for papers published after 2023 are currently being built.

[confproc] C. de la Higuera / 2000 / Current Trends in Grammatical Inference / Advances in Pattern Recognition. Joint IAPR International Workshops SSPR+SPR’2000 / Springer Verlag

[journal] E. Tanaka / 1995 / Theoretical aspects of synrtactic pattern recognition / Pattern Recognition 28(7) : 1053~1061

[journal] O. Unold / 2010 / Learning context-free grammar using improved tabular representation / Applied Soft Computing 10(1) : 44~52

[report] L. Lee / 1996 / Learning of context-free languages: A Survey of the Literature / Havard University

[journal] O. Unold / 2005 / Context-free grammar induction with grammar-based classifier system / Archives of Control Science 15(4) : 681~690

[journal] Y. Sakakibara / 2005 / Learning context-free grammars using tabular representations / Pattern Recognition 38 : 1372~1383

[confproc] R. C. Dharmik / 2016 / Ambiguity of Context Free Grammar using the CYK algorithm / 2016 World Conference on Futuristic Trends in Research and Innovation for Social Welfare

[book] Z. Michalewicz / 1999 / Genetic Algorithms + Data Structures = Evolution Programs / Springer

[journal] F. M. Massimo / 2020 / Parsing with CYK over Distributed Representations / Algorithms 13(10) : 262~

[journal] C. G. Nevill-Manning / 1997 / Identifying hierachical structure in sequences: a linear-time algorithm / Journal of Artificial Intelligence Ressearch : 67~82

[journal] D. Hrnčič / 2012 / A memetic grammar inference algorithm for language learning / Applied Soft Computing : 1006~1020

[journal] M. Alomari / 2021 / Online perceptual learning and natural language acquisition for autonomous robots / Artificial Intelligence 303

[book] A. v. Aho / 1972 / The Theory of Parsing and Compiling, vol. I: Parsing / Pentice-Hall

[journal] F. Denis / 2014 / Certified CYK parsing of context-free languages / Journal of Logical and Algebraic Methods in Programming September-November 83(5-6) : 459~468

[confproc] P. Adriaans / 2002 / Grammatical Inference: Algorithms and Applications / Proceedings of ICGI 00 / SPringer-Verlag

[web] A. Kádár / 2021 / Tutorial #15: Parsing I: context-free grammars and the CYK algorithm / https://www.borealisai.com/blog/tutorial-15-parsing

[other] J. Heinz / 2015 / Grammatical Inference for Computational Linguistics / Grammatical Inference for Computational Linguistics

[journal] Ž. Kovačević / 2020 / From Grammar Inference to Semantic Inference—An Evolutionary Approach / Mathematics 8(816) : 816~

[confproc] J. A. Laxminarayana / 2003 / Inference of a subclass of context-free grammars using positive samples / ECML/PKDD 2003 Workshop on Learning Context-Free Grammars : 29~40

[journal] A. Dubey / 2008 / Learning context-free grammar rules from a set of program / IET Software : 223~240

This paper was written with support from the National Research Foundation of Korea.

KJCKorea
Journal Central

Journal of The Korea Society of Computer and Information 2023 KCI Impact Factor : 0.65

Improved Method for Learning Context-Free Grammar using Tabular representation

ABSTRACT

KEYWORDS

Citation status

* References for papers published after 2023 are currently being built.

Journal of The Korea Society of Computer and Information 2023 KCI Impact Factor : 0.65

Improved Method for Learning Context-Free Grammar using Tabular representation

ABSTRACT

KEYWORDS

Statistics

Tools

Issue List

Citation status

KCI Citation Counts (0)

REFERENCES (20) * References for papers published after 2023 are currently being built.

Search PDF

Citation

* References for papers published after 2023 are currently being built.