Automata Theory Questions
A context-sensitive grammar is a formal grammar that allows rules to have context-dependent conditions on the left-hand side as well as the right-hand side. In other words, the production rules of a context-sensitive grammar can rewrite a nonterminal symbol into a string of terminal and nonterminal symbols, but the rewriting is subject to certain context conditions. These context conditions are typically expressed as restrictions on the surrounding symbols or the length of the string being rewritten. Context-sensitive grammars are more powerful than context-free grammars, as they can generate languages that cannot be generated by context-free grammars. They are often used to describe natural languages and programming languages.