\documentclass{bschlangaul-aufgabe}
\bLadePakete{formale-sprachen,chomsky-normalform,pumping-lemma}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 2},
  Thematik = {Nonterminale: STU, Terminale: abcde},
  Referenz = 66115-2017-F.T2-A2,
  RelativerPfad = Examen/66115/2017/03/Thema-2/Aufgabe-2.tex,
  ZitatSchluessel = examen:66115:2017:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Kontextfreie Sprache, Chomsky-Normalform, Pumping-Lemma (Kontextfreie Sprache)},
  EinzelpruefungsNr = 66115,
  Jahr = 2017,
  Monat = 03,
  ThemaNr = 2,
  AufgabeNr = 2,
}

\let\schrittE=\bChomskyUeberErklaerung

\begin{enumerate}
\item Gegeben\index{Kontextfreie Sprache}
\footcite{examen:66115:2017:03} sei die kontextfreie Grammatik \bGrammatik{} mit Sprache
L(G), wobei $V = {S, T, U}$ und \bAlphabet{a, b, c, d, e}. $P$ bestehe
aus den folgenden Produktionen:
\index{Chomsky-Normalform}

\begin{bProduktionsRegeln}
S -> U | S b U,
T -> d S e | a,
U -> T | U c T
\end{bProduktionsRegeln}
\bFlaci{Gib25c5oc}

\begin{enumerate}
%%
% a)
%%

\item Zeigen Sie $a c d a e \in L(G)$.

\begin{bAntwort}
\bAbleitung{
S ->
U ->
U c T ->
T c T ->
a c T ->
a c d S e ->
a c d U e ->
a c d a e}
\end{bAntwort}

%%
% b)
%%

\item Bringen Sie $G$ in Chomsky-Normalform.

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

\bNichtsZuTun

\item \schrittE{2}

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

\item \schrittE{3}

\begin{bProduktionsRegeln}
S -> D S E | a | U C T | S B U,
T -> D S E | a,
U -> D S E | a | U C T,
B -> b,
C -> c,
D -> d,
E -> e,
\end{bProduktionsRegeln}

\item \schrittE{4}
% S   -> S S.1 | T2 S.2 | a | U S.3
% T   -> T2 S.2 | a
% U   -> T2 S.2 | a | U S.3
% T1  -> b
% T2  -> d
% T3  -> e
% T4  -> c
% S.1 -> T1 U
% S.2 -> S T3
% S.3 -> T4 T

\begin{bProduktionsRegeln}
S -> D S_E | a | U C_T | S B_U, % S   -> S S.1 | T2 S.2 | a | U S.3
T -> D S_E | a, % T   -> T2 S.2 | a
U -> D S_E | a | U C_T, % U   -> T2 S.2 | a | U S.3
B -> b, % T1  -> b
C -> c, % T4  -> c
D -> d, % T2  -> d
E -> e, % T3  -> e
S_E -> S E, % S.2 -> S T3
C_T -> C T, % S.3 -> T4 T
B_U -> B U, % S.1 -> T1 U
\end{bProduktionsRegeln}
\end{enumerate}
\end{bAntwort}
\end{enumerate}

%%
%
%%

\item Geben Sie eine kontextfreie Grammatik für
\bAusdruck{a^i b^k c^i | i, k \in \mathbb{N}} an.

\begin{bAntwort}
Wir interpretieren $\mathbb{N}$ als $\mathbb{N}_0$.

\begin{bProduktionsRegeln}
S -> a S c | a B c | B | EPSILON
B -> b | B b
\end{bProduktionsRegeln}
\bFlaci{Ghp3bfdtg}
\end{bAntwort}

%%
%
%%

\item Zeigen Sie, dass \bAusdruck{a^i b^k c^i | i, k \in \mathbb{N}
\land i < k} nicht kontextfrei ist, indem Sie das Pumping-Lemma für
kontextfreie Sprachen anwenden.
\index{Pumping-Lemma (Kontextfreie Sprache)}

\begin{bExkurs}[Pumping-Lemma für Reguläre Sprachen]
\bPumpingKontextfrei
\end{bExkurs}

\begin{bAntwort}
\bMetaNochKeineLoesung
\end{bAntwort}

\end{enumerate}
\end{document}