Advertisement
Published in:
2022 | OriginalPaper | Chapter
Linear Bounded Automata and Context-Sensitive Grammars
Author : Alberto Pettorossi
Published in: Automata Theory and Formal Languages
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.