TY - GEN

T1 - Non-erasing variants of the Chomsky-Schützenberger theorem

AU - Okhotin, Alexander

PY - 2012/8/20

Y1 - 2012/8/20

N2 - The famous theorem by Chomsky and Schützenberger ("The algebraic theory of context-free languages", 1963) states that every context-free language is representable as h(D k ∩ R), where D k is the Dyck language over k ≥ 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.

AB - The famous theorem by Chomsky and Schützenberger ("The algebraic theory of context-free languages", 1963) states that every context-free language is representable as h(D k ∩ R), where D k is the Dyck language over k ≥ 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.

UR - http://www.scopus.com/inward/record.url?scp=84864982545&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-31653-1_12

DO - 10.1007/978-3-642-31653-1_12

M3 - Conference contribution

AN - SCOPUS:84864982545

SN - 9783642316524

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 121

EP - 129

BT - Developments in Language Theory - 16th International Conference, DLT 2012, Proceedings

T2 - 16th International Conference on Developments in Language Theory, DLT 2012

Y2 - 14 August 2012 through 17 August 2012

ER -