\documentclass{bschlangaul-aufgabe}
\bLadePakete{formale-sprachen,cyk-algorithmus}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 2},
  Thematik = {CYK mit Wort „aaaccbbb“},
  Referenz = 66115-2021-F.T1-TA1-A2,
  RelativerPfad = Examen/66115/2021/03/Thema-1/Teilaufgabe-1/Aufgabe-2.tex,
  ZitatSchluessel = examen:66115:2021:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {CYK-Algorithmus},
  EinzelpruefungsNr = 66115,
  Jahr = 2021,
  Monat = 03,
  ThemaNr = 1,
  TeilaufgabeNr = 1,
  AufgabeNr = 2,
}

\let\l=\bKurzeTabellenLinie

Sei \bGrammatik{} eine kontextfreie Grammatik mit Variablen $V =
\bMenge{S, A, B, C, D}$, Terminalzeichen \bAlphabet{a,b,c},
Produktionen\index{CYK-Algorithmus}
\footcite{examen:66115:2021:03}

\begin{bProduktionsRegeln}
S -> A D | C C | c,
A -> a,
B -> b,
C -> C C | c,
D -> S B | C B,
\end{bProduktionsRegeln}

\noindent
und Startsymbol $S$. Führen Sie den Algorithmus von Cocke, Younger und
Kasami (CYK-Algorithmus) für $G$ und das Wort $aaaccbbb$ aus. Liegt
$aaaccbbb$ in der durch $G$ erzeugten Sprache? Erläutern Sie Ihr
Vorgehen und den Ablauf des CYK-Algorithmus.

\begin{bAntwort}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
a   & a   & a   & c   & c   & b   & b   & b   \\\hline\hline
-   & -   & -   & S,C & D,D & -   & -   \l7
-   & -   & -   & D,D & -   & -   \l6
-   & -   & S,S & -   & -   \l5
-   & -   & D,D & -   \l4
-   & S,S & -   \l3
-   & D,D  \l2
S,S \l1
\end{tabular}

\bigskip

\noindent
Das Wort $aaaccbbb$ liegt in der Sprache.
\end{bAntwort}

\end{document}