D-graphs in context-free language theory

Article type: Research Article

Authors: Stanevičienė, Larisa

Affiliations: Moscow State University, Department of Computational Mathematics and Cybernetics, Akademika Vargi 8–112, Moscow, Russia. E-mail:stanev@ccas.ru

Abstract: The paper present a proposed approach in the context-free language theory. The main new notion is a graph defining a pushdown automaton (PDA). Each vertex of such graph is a pair (state, stack symbol). Each edge corresponds to a “command” and is labelled by input portion being read by the command and by a “charge” describing the stack word transformation. Some paths of the graph represent PDA's computations. The finite automata are a case of the pushdown graphs. The paper contains some of the author's results based on the approach – the notion of a D-language extending the notion of Dyck's language and the theorem on a representation of a context-free language as a morphical image of the intersection of a D-language with a local set.

Keywords: pushdown automata, graphic characterization of context-free languages, morphic characterization of context-free languages

DOI: 10.3233/INF-1997-8103

Journal: Informatica, vol. 8, no. 1, pp. 43-56, 1997