Some new representations of arbitrary recursively enumerable (r.e.) languages in terms of morphisms mapping strings to strings are proven. The authors refer to similar results by Geffert [1], but they soon reveal that chapter 6 of Salomaa’s Jewels of formal language theory [2] is their main source of inspiration. That chapter shows various ways of representing regular, context-free, and r.e. languages using morphisms and inverse morphisms. The results in this paper are sharpened representations, using refinements of techniques used by Salomaa.

Two of the authors’ results are as follows. Their theorem 3 states that, for every r.e. language L ⊆ &Sgr;*, alphabets H and &Ggr; and nonerasing morphisms g , h : H* → &Ggr;* exist such that L = { w ∈ &Sgr;* | ∃ z ∈ H ⁺ such that g ( z ) = h ( z ) w }. Theorem 4 states that, for every r.e. language L ∈ &SGr;*, a linear context-free grammar G exists such that L = &rgr; ( L ( G ) ) ∩ &Sgr;*, where &rgr; is the Dyck reduction cancelling all occurrences of a ā and A Ā, where a is some fixed letter of &Sgr;, ā ∉ &Sgr; is another terminal of G, and A and Ā are fixed nonterminals of G.