×

A unified approach to characterizations of recursively enumerable languages. (English) Zbl 0756.68065

Summary: Starting from an arbitrary phrase structure grammar \(G\) we construct two morphisms such that several well known representations of \(L(G)\) are obtained in a unified and easy way. These include characterizations in terms of the quotient operation [(*) V. Geffert, Theor. Comput. Sci. 62, No. 3, 235-249 (1988; Zbl 0664.68075)], Post normal systems [M. Minsky, Computation: Finite and infinite machines, Prentice- Hall, Englewood Cliffs, N.J. (1967) and E. Post, A variant of a recursively unsolvable problem, Bull. Am. Math. Soc. 52, 264-268 (1946)], and minimal equality sets [K. Culik II, J. Assoc. Comput. Math. 26, 345-350 (1979; Zbl 0395.68076)]. Representations in terms of linear context-free grammars [B. S. Baker and R. V. Book, J. Comput. System Sci. 8, 315-332 (1974; Zbl 0309.68043)], various pushdown devices [V. Geffert, Lect. Notes Comput. Sci. 324, 309-317 (1988; Zbl 0652.68095); M. Latteux and P. Turakainen, Acta Inf. 28, 179- 186 (1990; Zbl 0715.68049) and W. J. Savitch, Siam J. Comput. 2, 174-182 (1973; Zbl 0298.68057)], equality sets [J. Engelfriet and G. Rozenberg, Inf. Control 43, 20-49 (1979; Zbl 0422.68034); J. Engelfriet and G. Rozenberg, J. Assoc. Comput. Mach. 27, 499- 518 (1980; Zbl 0475.68047) and A. Salomaa, Acta Cybern. 4, 127-139 (1978; Zbl 0407.68077)] and grammars in a special normal for are easy consequences [M. Latteux and P. Turakainen, Acta Inf. 28, 179-186 (1990; Zbl 0715.68049)]. The undecidability of the Post correspondence problem follows directly from the first characterization, the proof of which is really short compared with the original one in (*).

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite