On purely morphic characterizations of context-free languages (Q1098315)

The author shows that for any \(\lambda\)-free context-free language L there effectively exist a weak coding g and a homomorphism h such that \(L=gh^{-1}({\mathfrak c}D_ 2)\), where \(D_ 2\) is the Dyck set over a two-letter alphabet, and \({\mathfrak c}\) is a specific letter. This characterization can be considered as a refinement of the corresponding result by the author and \textit{D. Wood} [Inform. Sci. 33, 209-215 (1984; Zbl 0565.68073)]. It also follows that for each recursively enumerable language K there exist an alphabet T, a weak identity g, a coding f and a homomorphism h such that \(K=g(D\cap f(h^{-1}({\mathfrak c}D_ 2)))\), where D is the Dyck set over T.