In type 1 {Context Sensitive Grammars}, rules start with variables, and productions are the same length or longer. Rules depend on nearby symbols. Context-sensitive grammars are equivalent to Linear Bounded Automata {non-deterministic Turing Machine}, which have left and right end markers that have no replacements and so bound strings. Context-sensitive grammars are recursive. Context-sensitive grammar-recognition algorithms are Pspace-complete and so can never complete. Context-free grammars plus symbol tables can model context-sensitive grammars.
Social Sciences>Linguistics>Grammar>Kinds>Quantitative>Formal
6-Linguistics-Grammar-Kinds-Quantitative-Formal
Outline of Knowledge Database Home Page
Description of Outline of Knowledge Database
Date Modified: 2022.0224