\section{Kontextfreie Sprache \hfill {\small 5 Punkte}}

\begin{enumerate}[a)]
\item Geben Sie die rekursive Definition des CYK-Algorithmus formal an:
  \begin{enumerate}
  \item[$i = j$] \[ V(i, i) := \]
  \item[$i < j$] \[ V(i, j) := \]
  \end{enumerate}
  
\item Gegeben Sei die folgende Grammatik
  $G = (V, \Sigma, \mathcal{P}, \mathcal{S})$,
  \begin{align*}
    \mathcal{S} &\rightarrow AB | DB \\
    A &\rightarrow a  \\
    B &\rightarrow b\\
    C &\rightarrow AB | DB \\
    B &\rightarrow AC
  \end{align*}

  Vervollständigen Sie die Tabelle für die Eingabe $w = $
  \texttt{aaabbb} an den Stellen $V(i, j)$. Ist das Wort $w$ in der
  Sprache $L(G)$ enthalten? Wie wissen sie dies?

  \vspace{1cm}
  
  \begin{center}
    \begin{tikzpicture}
      \matrix(M)[
      matrix of nodes,
      row sep=-\pgflinewidth,
      column sep=-\pgflinewidth,
      nodes={draw,minimum width=1.5cm,minimum height=1.5cm}
      ]{
        \{A\}&\{A\}&\{A\}&\{B\}&\{B\}&\{B\}\\
        \{\}&\{\}&\{S,C\}&\{\}&\{\}\\
        \{\}&\{D\}&\{\}&\{\}\\
        \{\}&\{S,C\}&\{\}\\
        $V(1, 5)$&$V(2, 6)$\\
        $V(1, 6)$\\
      };
      
      \begin{scope}[font=\ttfamily{}]
        \node[above=4pt of M-1-1] {a};
        \node[above=4pt of M-1-2] {a};
        \node[above=4pt of M-1-3] {a};
        \node[above=4pt of M-1-4] {b};
        \node[above=4pt of M-1-5] {b};
        \node[above=4pt of M-1-6] {b};
      \end{scope}         
    \end{tikzpicture}
  \end{center}
\end{enumerate}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "master"
%%% End: