2022 | OriginalPaper | Buchkapitel
Linear Bounded Automata and Context-Sensitive Grammars
verfasst von : Alberto Pettorossi
Erschienen in: Automata Theory and Formal Languages
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
In this chapter we first show that the notions of the context-sensitive grammars and the type 1 grammars are equivalent. Then we show that every context-sensitive language is a recursive set. Finally, we introduce the class of the linear bounded automata and we show that this class of automata is characterized by the fact that it accepts the set of the context-sensitive languages.