On characterizations of recursively enumerable languages

Summary

Geffert has shown that earch recursively enumerable languageL overΣ can be expressed in the formL{h(x) ⁻¹ g(x)∣x inΔ ⁺}∩Σ ^* whereΔ is an alphabet andg, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert's result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations ofL. For instance,L =ρ(L ₀)∩Σ ^* whereL ₀ is a minimal linear language and ρ is the Dyck reductionaā→ε, AĀ→ε.