\begin{frame}{Context-Sensitive Grammars} \begin{block}{} A grammar is \emph{context-sensitive} if for every rule $x \to y$ it holds: \begin{talign} |x|\leq|y| \quad \text{(and $x \neq \lambda$)} \end{talign} \end{block} \emph{Note}: the words cannot get shorter during derivation. \pause\bigskip \begin{goal}{} For every context-sensitive grammar $G_1$\\ there exists a grammar~$G_2$ with rules of the form \begin{talign} xAy \to xvy \quad \text{with} \quad v \neq \lambda \end{talign} such that $L(G_1) = L(G_2)$. \end{goal} (Compare with the shape of rules in a context-free grammar.) \pause\bigskip \begin{block}{} A language $L$ is \emph{context-sensitive} if there exists a context-sensitive grammar $G$ with $L(G) = L \setminus \{\, \lambda \,\}$. \end{block} \end{frame}