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

Krasimir Yordzhev

doi:doi:10.11648/j.ajam.20130101.12

| Peer-Reviewed

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

Krasimir Yordzhev

Published in American Journal of Applied Mathematics (Volume 1, Issue 1)

Received: 27 March 2013 Accepted: Published: 2 April 2013

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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), 2024. 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

Plain Text BibTeX RIS

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

Krasimir Yordzhev

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

Download PDF

Sections

Plain Text BibTeX RIS

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