Definition 7.1.1: for a given set of non-terminals V and set of terminals _, a production is context-sensitive if it is of the form _A_ _ ___, where A_V, ____(V__)*, and __(V__)+; a grammar is context-sensitive if all its productions are.
Definition 7.1.2: L ___* is an _-free context-sensitive language if there exists a context-sensitive grammar G so that L = L(G); L is a context-sensitive language if there exists a context-sensitive grammar G so that either L = L(G) or L = L(G) _ {_} [in this latter case we may write L = L_(G)].
Since we have previously proven that erasing rules can be eliminated in context-free grammars, each context-free language is context-sensitive.
| Next slide | Back to first slide | View graphic version |