×

On the transition graphs of automata and grammars. (English) Zbl 0768.68124

Graph-theoretic concepts in computer science, Proc. Int. Workshop, Berlin/Germany 1990, Lect. Notes Comput. Sci. 484, 311-337 (1992).
[For the entire collection see Zbl 0747.00042.]
A pushdown automaton on the sets \(\Sigma\) of terminals, \(X\) of stack letters and \(Q\) of states, is a finite set of rules \(pA@>f>>q\alpha\) labelled by \(f\in \Sigma\cup\{\varepsilon\}\), making the automaton move from state \(p\) to state \(q\), and the stack letter \(A\) change into the stack word \(\alpha\). such a rule defines the automaton transitions \(pA\beta@>f>>q\alpha\beta\), reaplacing the top \(A\) of the stack \(A\beta\) by a word \(\alpha\). The set of transitions obtained from any axiom in \(QX^*\) is a pushdown transition graph or a context-free graph in the sense of D. E. Muller and P. E. Schupp [Theor. comput. Sci. 37, 51-55 (1985; Zbl 0605.03005)]. A context-free grammar may be viewed as a pushdown automaton with one state, which can be omitted because it is irrelevant. The grammar rules have then the form \(A@>f>>\alpha\), and any transition graph is called alphabetic. Therefore, every alphabetic graph is a pushdown transition graph. But there exist pushdown transition graphs which are not alphabetic.
First, we show (in section 1) that pushdown transition graphs can effectively be generated from deterministic graph grammars. From this, we can decide (in section 2) if a pushdown transition graph is alphabetic, and we can then transform this automaton into a context-free grammar with the same transition graph.
Last, we show (in section 3) that there exist pushdown transition graphs whose structure is comparable with no alphabetic graph, in the bisimulation meaning, see D. Park [Theoretical computer science, 5th GI-Conf., Karlsruhe 1981, Lect. Notes Comput. Sci. 104, 167-183 (1981; Zbl 0457.68049)]. To do so, we consider their canonical graphs obtained as quotient by their greatest self-bisimulation. Then and in an effective way, we establish that the canonical graphs of the alphabetic graphs are always alphabetic. But, we give a pushdown transition graph whose canonical graph is not a pushdown transition graph.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite