\documentclass{bschlangaul-aufgabe}
\bLadePakete{formale-sprachen,chomsky-normalform}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 3},
  Thematik = {Nonterminale: STU, Terminale: ab},
  Referenz = 66115-2019-F.T1-A3,
  RelativerPfad = Examen/66115/2019/03/Thema-1/Aufgabe-3.tex,
  ZitatSchluessel = examen:66115:2019:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Kontextfreie Sprache, Chomsky-Normalform},
  EinzelpruefungsNr = 66115,
  Jahr = 2019,
  Monat = 03,
  ThemaNr = 1,
  AufgabeNr = 3,
}

\let\schrittE=\bChomskyUeberErklaerung

Gegeben sei die kontextfreie Grammatik \bGrammatik{} mit Sprache
$L(G)$, wobei $V = \bMenge{S,T,U}$ und \bAlphabet{a,b}. $P$ bestehe
aus den folgenden Produktionen:
\index{Kontextfreie Sprache}
\footcite{examen:66115:2019:03}

\begin{bProduktionsRegeln}
S -> T U U T,
T -> a T | EPSILON,
U -> b U b | a,
\end{bProduktionsRegeln}
\bFussnoteUrl{https://flaci.com/Gjpsin26a}
\begin{enumerate}

%%
% (a)
%%

\item Geben Sie fünf verschiedene Wörter $w \in \Sigma^*$ mit $w \in
L(G)$ an.

\begin{bAntwort}
\begin{itemize}
\item aa
\item aaaa
\item ababbaba
\item aababbabaa
\item abbabbbbabba
\end{itemize}
\end{bAntwort}

%%
% (b)
%%

\item Geben Sie eine explizite Beschreibung der Sprache $L(G)$ an.

\begin{bAntwort}
\bAusdruck{a^* b^n a b^{2n} a b^n a^*}{n \in \mathbb{N}_0}
\end{bAntwort}

%%
% (c)
%%

\item Bringen Sie $G$ in Chomsky-Normalform und erklären Sie Ihre
Vorgehensweise.
\index{Chomsky-Normalform}

\begin{bAntwort}
\begin{enumerate}
\item \schrittE{1}

\begin{bProduktionsRegeln}
S -> T U U T | T U U | U U T | U U,
T -> a T | a,
U -> b U b | a,
\end{bProduktionsRegeln}

\item \schrittE{2}

\bNichtsZuTun

\item \schrittE{3}

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

\item \schrittE{4}

% S   -> T S.1 | U S.2 | T S.4 | U U
% T   -> T1 T | a
% U   -> T2 U.1 | a
% T1  -> a
% T2  -> b
% S.1 -> U S.2
% S.2 -> U T
% S.4 -> U U
% U.1 -> U T2

\begin{bProduktionsRegeln}
S -> T S_1 | T S_3 | U S_2 | U U, % S   -> T S.1 | U S.2 | T S.4 | U U
S_1 -> U S_2, % S.1 -> U S.2
S_2 -> U T, % S.2 -> U T
S_3 -> U U, % S.4 -> U U
T -> A T | a, % T   -> T1 T | a
U -> B U_1 | a, % U   -> T2 U.1 | a
U_1 -> U B, % U.1 -> U T2
A -> a, % T1  -> a
B -> b, % T2  -> b
\end{bProduktionsRegeln}
\end{enumerate}

\end{bAntwort}

\end{enumerate}
\end{document}