zbMATH — the first resource for mathematics

Non-erasing variants of the Chomsky-Schützenberger theorem. (English) Zbl 1370.68211
Yen, Hsu-Chun (ed.) et al., Developments in language theory. 16th international conference, DLT 2012, Taipei, Taiwan, August 14–17, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-31652-4/pbk). Lecture Notes in Computer Science 7410, 121-129 (2012).
Summary: The famous theorem by N. Chomsky and M. P. Schützenberger [in: Computer programming and formal systems, Stud. Logic Found. Math., 118–161 (1963; Zbl 0148.00804)] states that every context-free language is representable as \(h(D _{k } \cap R)\), where \(D _{k }\) is the Dyck language over \(k \geqslant 1\) pairs of brackets, \(R\) is a regular language and \(h\) is a homomorphism. This paper demonstrates that one can use a non-erasing homomorphism in this characterization, as long as the language contains no one-symbol strings. If the Dyck language is augmented with neutral symbols, the characterization holds for every context-free language using a letter-to-letter homomorphism.
For the entire collection see [Zbl 1248.68052].

68Q70 Algebraic theory of languages and automata
Full Text: DOI