For any context-free grammar, we build a transition diagram, that is, a finite directed graph with labeled arcs, which describes the work of the grammar. This approach is new, and it is different from previously known graph models. We define the concept of proper walk in this transition diagram and we prove that a word belongs to a given context-free language if and only if this word can be obtained with the help of a proper walk.
Published in | American Journal of Applied Mathematics (Volume 1, Issue 1) |
DOI | 10.11648/j.ajam.20130101.12 |
Page(s) | 8-11 |
Creative Commons |
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited. |
Copyright |
Copyright © The Author(s), 2013. Published by Science Publishing Group |
Context-Free Grammar, Finite Digraph, Transition Diagram, Proper Walk, Chomsky Normal Form
[1] | A.V. Aho, J.D. Ullman, The theory of parsing, translation and computing. Vol. 1, 2, Prentice-Hall, 1972. |
[2] | J.E. Hopcroft, R. Motwani, J.D. Ullman, Introduction to automata theory, languages, and computation. Addison-Wesley, 2001. |
[3] | G. Lallemant, Semigroups and combinatorial applications. John Wiley & Sons, 1979. |
[4] | I. Mirchev, Graphs. Optimization algorithms in networks. SWU "N. Rilsky", Blagoevgrad, 2001. |
[5] | M. Swami, K. Thulasirman, Graphs, networks and algorithms. John Wiley & Sons, 1981. |
[6] | K. Yordzhev, An n2 Algorithm for Recognition of Context-free Languages. Cybern. Syst. Anal. 29, No.6, (1993), 922-927. |
[7] | K. Yordzhev, Inclusion of Regular and Linear Languages in Group Languages. International J. of Math. Sci. & Engg. Appls. (IJMSEA) ISSN 0973-9424, Vol. 7 No. I ( 2013), 323-336. |
APA Style
Krasimir Yordzhev. (2013). A Representation of Context-free Grammars with the Help of Finite Digraphs. American Journal of Applied Mathematics, 1(1), 8-11. https://doi.org/10.11648/j.ajam.20130101.12
ACS Style
Krasimir Yordzhev. A Representation of Context-free Grammars with the Help of Finite Digraphs. Am. J. Appl. Math. 2013, 1(1), 8-11. doi: 10.11648/j.ajam.20130101.12
AMA Style
Krasimir Yordzhev. A Representation of Context-free Grammars with the Help of Finite Digraphs. Am J Appl Math. 2013;1(1):8-11. doi: 10.11648/j.ajam.20130101.12
@article{10.11648/j.ajam.20130101.12, author = {Krasimir Yordzhev}, title = {A Representation of Context-free Grammars with the Help of Finite Digraphs}, journal = {American Journal of Applied Mathematics}, volume = {1}, number = {1}, pages = {8-11}, doi = {10.11648/j.ajam.20130101.12}, url = {https://doi.org/10.11648/j.ajam.20130101.12}, eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajam.20130101.12}, abstract = {For any context-free grammar, we build a transition diagram, that is, a finite directed graph with labeled arcs, which describes the work of the grammar. This approach is new, and it is different from previously known graph models. We define the concept of proper walk in this transition diagram and we prove that a word belongs to a given context-free language if and only if this word can be obtained with the help of a proper walk.}, year = {2013} }
TY - JOUR T1 - A Representation of Context-free Grammars with the Help of Finite Digraphs AU - Krasimir Yordzhev Y1 - 2013/04/02 PY - 2013 N1 - https://doi.org/10.11648/j.ajam.20130101.12 DO - 10.11648/j.ajam.20130101.12 T2 - American Journal of Applied Mathematics JF - American Journal of Applied Mathematics JO - American Journal of Applied Mathematics SP - 8 EP - 11 PB - Science Publishing Group SN - 2330-006X UR - https://doi.org/10.11648/j.ajam.20130101.12 AB - For any context-free grammar, we build a transition diagram, that is, a finite directed graph with labeled arcs, which describes the work of the grammar. This approach is new, and it is different from previously known graph models. We define the concept of proper walk in this transition diagram and we prove that a word belongs to a given context-free language if and only if this word can be obtained with the help of a proper walk. VL - 1 IS - 1 ER -