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

\let\m=\bMenge
\let\schrittE=\bChomskyUeberErklaerung

Gegeben ist die kontextfreie Grammatik \bGrammatik{} mit
\bAlphabet{a,b}, $N = \m{S, A, B}$ und\index{Chomsky-Normalform}
\footcite{examen:66115:2012:03}

\begin{bProduktionsRegeln}
S -> A,
S -> B,
A -> a A b,
B -> A A,
B -> b B a,
A -> a
\end{bProduktionsRegeln}
\bFlaci{Gr3rgt2vg}

\noindent
Geben Sie eine äquivalente Grammatik in Chomsky-Normalform an.

\begin{bAntwort}
Kann auch so geschrieben werden:
\begin{bProduktionsRegeln}
S -> A | B,
A -> a A b | a,
B -> A A | b B a,
\end{bProduktionsRegeln}

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

\bNichtsZuTun

\item \schrittE{2}

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

\item \schrittE{3}

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

\item \schrittE{4}

% Ergebnis von Flaci.com:
%      S   -> T1 S.1 | a | A A | T2 S.2
%      A   -> T1 S.1 | a
%      B   -> A A | T2 S.2
% T_a: T1  -> a
% T_b: T2  -> b
% C:   S.1 -> A T2
% D:   S.2 -> B T1

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

\end{enumerate}
\end{bAntwort}

\end{document}