2011 | OriginalPaper | Buchkapitel
Morphic Characterizations in Terms of Insertion Systems with a Context of Length One
verfasst von : Kaoru Fujioka
Erschienen in: Developments in Language Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Representing a class of languages through operations on its subclasses is a traditional issue within formal language theory. Among the variety of representation theorems for context-free languages, Chomsky-Schützenberger theorem is unique in that it consists of Dyck languages, regular languages, and simple operations. In this work, we obtain some characterizations and representation theorems of context-free languages and regular languages in Chomsky hierarchy by insertion systems, strictly locally testable languages, and morphisms in the framework of Chomsky-Schützenberger theorem.