A note on morphic characterization of languages

AbstractIt is noted, by using ideas of Culik, Fich and Salomaa [3], that for each language L and each regular language R the language L ∩ R is obtained from L# by applying the operation ‘a morphism followed by an inverse morphism' twice. As a consequence new purely morphic characterizations, based on the Dyck language D2 and the twin-shuffle language L2, are derived for the families of context-free and recursively enumerable languages, respectively. Also a morphic representation result for rational transductions follows