\documentclass{bschlangaul-aufgabe}
\bLadePakete{formale-sprachen,pumping-lemma}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 2},
  Thematik = {w w1 w w2},
  Referenz = 66115-2021-F.T2-TA1-A2,
  RelativerPfad = Examen/66115/2021/03/Thema-2/Teilaufgabe-1/Aufgabe-2.tex,
  ZitatSchluessel = examen:66115:2021:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Kontextfreie Sprache, Pumping-Lemma (Kontextfreie Sprache)},
  EinzelpruefungsNr = 66115,
  Jahr = 2021,
  Monat = 03,
  ThemaNr = 2,
  TeilaufgabeNr = 1,
  AufgabeNr = 2,
}

\begin{enumerate}

%%
% a)
%%

\item Zeigen Sie, dass die Sprache
\index{Kontextfreie Sprache}
\footcite{examen:66115:2021:03}

\begin{center}
\bAusdruck{w w_1 w w_2}{w, w_1, w_2
\in \{ a,b,c \}^* \text{ und } 2|w| \geq |w_1| + |w_2|}
\end{center}

nicht kontextfrei
ist. \index{Pumping-Lemma (Kontextfreie Sprache)}

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

\begin{bAntwort}
Es gibt eine Pumpzahl. Sie sei $j$. $a^j b^j a^j c^j$ ist ein Wort aus
$L$, das sicher länger als $j$ ist. Außerdem gilt $2|a^j| \geq |b^j| +
|c^j|$. Unser gewähltes Wort ist deshalb in $L$.

Da $|vwx| \leq j$ und $|xv| \geq 1$ sein muss, liegt $vwx$ entweder in
$w$, $w_1$ oder $w_2$.

\bPseudoUeberschrift{Aufteilung: $vwx$ in $w$ (erstes $w$):}

\begin{description}
\item[u]: $\varepsilon$
\item[v]: $a$
\item[w]: $a^{j - 2}$
\item[x]: $a$
\item[y]: $b^j a^j c^j$
\end{description}

Es gilt $uv^iwx^iy \notin L$ für alle $i \in \mathbb{N}_0$, da $a^j
b^j a^j c^j \notin L$ für $i = 0$, da
$|a^{j-2}| + |a^j| < |b^j| + |c^j|$

\bPseudoUeberschrift{Aufteilung: $vwx$ in $w$ (zweites $w$):}

\begin{description}
\item[u]: $a^j b^j$
\item[v]: $a$
\item[w]: $a^{j - 2}$
\item[x]: $a$
\item[y]: $c^j$
\end{description}

Es gilt $uv^iwx^iy \notin L$ für alle $i \in \mathbb{N}_0$, da $a^j
b^j a^j c^j \notin L$ für $i = 0$, da
$|a^j| + |a^{j-2}| < |b^j| + |c^j|$

\bPseudoUeberschrift{Aufteilung: $vwx$ in $w_1$:}

\begin{description}
\item[u]: $a^j$
\item[v]: $b$
\item[w]: $b^{j - 2}$
\item[x]: $b$
\item[y]: $a^j c^j$
\end{description}

Es gilt nicht $uv^iwx^iy \in L$ für alle $i \in \mathbb{N}_0$, da $a^j
b^j a^j c^j \notin L$ für alle $i > 2$ da
$2|a^j| < |b^{j - 2 + 2i}| + |c^j|$ für alle $i > 2$

\bPseudoUeberschrift{Aufteilung: $vwx$ in $w_2$:}

Analog zur Aufteilung $vwx$ in $w_1$

\Rightarrow $L$ ist nicht kontextfrei.
\end{bAntwort}

%%
% b)
%%

\item Betrachten Sie die Aussage

\bigskip

\centerline{Seien $L_1, \dots, I_n$ beliebige kontextfreie Sprachen.}

\centerline{Dann ist $\bigcap_{i=1}^n, L_i$ immer eine entscheidbare
Sprache.}

\bigskip

Entscheiden Sie, ob diese Aussage wahr ist oder nicht und begründen Sie
Ihre Antwort.

\begin{bAntwort}
Diese Aussage ist falsch.

Kontextfreie Sprachen sind nicht abgeschlossen unter dem Schnitt, \dh
die Schnittmenge zweier kontextfreier Sprachen kann in einer Sprache
eines anderen Typs in der Chomsky Sprachen-Hierachie resultieren.
Entsteht durch den Schnitt eine Typ-0-Sprache, dann ist diese nicht
entscheidbar.
\end{bAntwort}

%%
% c)
%%

\item Sei $\mathbb{N}_0 = \bMenge{0,1,2,\dots}$ die Menge der nicht
negativen natürlichen Zahlen. Es ist bekannt, dass \bAusdruck{a^n b^n
c^n}{n \in \mathbb{N}} keine kontextfreie Sprache ist. Ist die
Komplementsprache $L_5 = \{a, b, c \}^* \setminus \, L$ kontextfrei?
Begründen Sie Ihre Antwort.

\end{enumerate}
\end{document}