\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}