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.

Original languageEnglish
Title of host publicationDevelopments in Language Theory - 16th International Conference, DLT 2012, Proceedings
Pages121-129
Number of pages9
DOIs
StatePublished - 20 Aug 2012
Event16th International Conference on Developments in Language Theory, DLT 2012 - Taipei, Taiwan, Province of China
Duration: 14 Aug 201217 Aug 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7410 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Conference on Developments in Language Theory, DLT 2012
Country/TerritoryTaiwan, Province of China
CityTaipei
Period14/08/1217/08/12

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 41139545