| Peer-Reviewed

A Representation of Context-free Grammars with the Help of Finite Digraphs

Published: 2 April 2013
Views:       Downloads:
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.

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

Keywords

Context-Free Grammar, Finite Digraph, Transition Diagram, Proper Walk, Chomsky Normal Form

References
[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.
Cite This Article
  • 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

    Copy | Download

    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

    Copy | Download

    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

    Copy | Download

  • @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}
    }
    

    Copy | Download

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

    Copy | Download

Author Information
  • Faculty of Mathematics and Natural Sciences, South-West University, Blagoevgrad, Bulgaria

  • Sections