2013/05/29 by Krasimir Yordzhev · 1 citation
Computer Science · #cs.FL
published as American Journal of Applied Mathematics. Vol. 1, No. 1, 2013, pp. 8-11 · 4 figures
arxiv created 2013/05/29 · arxiv updated 2013/05/30
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.