\documentclass{bschlangaul-aufgabe}
\bLadePakete{formale-sprachen,cyk-algorithmus}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 5},
  Thematik = {CYK mit fehlenden Zellen (T: SABC N: ab)},
  Referenz = 66115-2017-H.T2-A5,
  RelativerPfad = Examen/66115/2017/09/Thema-2/Aufgabe-5.tex,
  ZitatSchluessel = examen:66115:2017:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {CYK-Algorithmus},
  EinzelpruefungsNr = 66115,
  Jahr = 2017,
  Monat = 09,
  ThemaNr = 2,
  AufgabeNr = 5,
}

\let\l=\bKurzeTabellenLinie

% Sei \bGrammatik{}
% eine kontextfreie Grammatik {V: Variablenmenge; S: Menge der Terminalsym
% bole; S: Startsymbol; P: Menge der Produktionen) in Chomsky-Normalform, und sei w — Wi... Wn
% ein Wort aus n Zeichen aus E. Der Algorithmus von Cocke/Younger/Kasami (CYK-Algorithmus)
% berechnet für alle i,j G {1,...,n}, i < j, die Variablenmenge V(i,j) = {A G V j A —)■
% . . . wj}.

Sei \bGrammatik{variablen={S, A, B, C}, alphabet={a, b}} die
kontextfreie Grammatik in Chomsky-Normalform und der Menge P der
Produktionen:\index{CYK-Algorithmus}
\footcite{examen:66115:2017:09}

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

\noindent
Sei $\omega = baaab$. Folgende Tabelle entsteht durch Anwendung des
CYK-Algorithmus. \ZB bedeutet $B \in V(3,5)$, dass aus der Variablen
$B$ das Teilwort $\omega_3 \omega_4 \omega_5 = aab$ hergeleitet werden
kann. Drei Einträge wurden weggelassen.

\begin{enumerate}

%%
% i)
%%
\item Bestimmen Sie die Mengen $V(1,2)$, $V(1,3)$ und $V(1,5)$.

\begin{bAntwort}
\begin{tabular}{|c|c|c|c|c|}
b     & a     & a   & a   & b \\\hline\hline

B     & A,C   & A,C & A,C & B \l5
A,S   & B     & B   & S,C \l4
-     & S,C,A & B \l3
S,A,C & S,C \l2
S,C \l1
\end{tabular}
\end{bAntwort}

%%
% ii)
%%

\item Wie entnehmen Sie dieser Tabelle, dass $\omega \in L(G)$ ist?

\begin{bAntwort}
In der Menge $V(1,5)$ ist das Startsymbol $S$ der Sprache $L(G)$
enthalten.
\end{bAntwort}

\end{enumerate}
\end{document}