\defineUnit{grammatik}{%
\begin{frame}
    \frametitle{Grammatiken}
    \setbeamercovered{dynamic}

    \begin{definition}[Grammatik]
        Eine \structure{(Phrasenstruktur-)Grammatik} $G = (V, \Sigma, P, S)$ ist ein 4-Tupel:
        \begin{description}
            \item[V] endlich viele \alert{Nichtterminale} (Variablen)
            \item[$\Sigma$] ein Alphabet von \alert{Terminalen}
            \item[P] endlich viele \alert{Produktionen} $\subseteq \left( V \cup \Sigma \right)^* \times \left( V \cup \Sigma \right)^*$
            \item[S] ein \alert{Startsymbol} (Axiom)
        \end{description}
        Ist $(l, r) \in P$, so schreibt man \structure{$l \rightarrow r$}.
    \end{definition}

    \vfill

    \begin{example}[]
        $\Sigma = \left\{ 0, 1 \right\}$. Grammatik für alle Wörter ungerader Länge, bei denen alle Nullen vor der ersten Eins stehen und weniger Nullen als Einsen vorhanden sind.
        \visible<2>{
            \begin{align}
                S \rightarrow 0S1 \mid S11 \mid 1
            \end{align}
        }
    \end{example}
\end{frame}
}

\defineUnit{ableitung}{%
\begin{frame}
    \frametitle{Ableitungsrelation}
    \setbeamercovered{dynamic}

    \begin{definition}[Ableitungsrelation]
        Eine Grammatik $G$ induziert eine \structure{Ableitungsrelation} $\rightarrow_G$ auf Wörtern über $V \cup \Sigma$. Seien $x, y$ solche Wörter und
        \begin{align}
            z &= x\alert{\alpha}y\\
            z^\prime &= x\alert{\beta}y\\
            \intertext{Dann ist}
            z &\rightarrow_G z^\prime
        \end{align}
        gdw. es eine Regel $\alert{\alpha \rightarrow \beta}$ in $P$ gibt.
    \end{definition}

    \vfill

    \begin{example}[]
        Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$:
        \begin{align*}
            S &\rightarrow_G 0S1 \rightarrow_G 00S11 \rightarrow_G 00S1111 \rightarrow_G 0011111 \\
            \intertext{Es gilt also}
            S &\rightarrow_G^* 0011111
        \end{align*}
    \end{example}
\end{frame}
}

\defineUnit{sprachtypen}{%
\begin{frame}
    \frametitle{Sprachtypen}

    Sei $G = (V, \Sigma, P, S)$ eine Grammatik und $\alpha \rightarrow \beta \in P$ beliebig.
    \begin{definition}[Monotonie]
        $G$ heißt \structure{(längen-)monoton}, wenn für $\alpha \neq S$ gilt
        \begin{align}
            \alert{\abs{\alpha} \leq \abs{\beta}}
        \end{align}
        und falls $S \to \epsilon \in P$, dann kommt $S$ nie auf der rechten Seite vor.
    \end{definition}

    \vfill

    \begin{definition}[Chomsky-Typen]
        Seien $A \in V$, $\gamma, \delta \in (V \cup \Sigma)^*$ und $\beta^\prime \in (V \cup \Sigma)^+$.\\
        Damit $G$ vom \structure{Typ k} ist, muss für $\alpha$ und $\beta$ gelten
        \begin{center}
            \tabulinesep=4pt
            \begin{tabu} to .8\textwidth{X[1,c,m]|[.5pt]X[2,c,m]X[2,c,m]}
                & $\alpha$ & $\beta$\\\tabucline[.5pt]{-}
                \structure{Typ 0} & beliebig & beliebig\\
                \structure{Typ 1} & $= \alert{\gamma} A \alert{\delta}$ & $= \alert{\gamma} \beta^\prime \alert{\delta}$\\
                \structure{Typ 2} & $\in V$ & beliebig\\
                \structure{Typ 3} & $\in V$ & $\in \Sigma^+ \cup \Sigma^*V$\\
            \end{tabu}
        \end{center}
        Ab Typ 1 muss $G$ auch \alert{monoton} sein.
    \end{definition}
\end{frame}
}

\defineUnit{cfl}{%
\begin{frame}[c]
    \frametitle{Kontextfreie Sprache}
    \setbeamercovered{dynamic}

    \begin{definition}[Kontextfreie Sprache]
        Eine kontextfreie Grammatik $G = (V, \Sigma, P, S)$ \alert{erzeugt} die Sprache
        \[
            L(G) := \left\{ w \in \Sigma^* \mid S \rightarrow_G^* w \right\}
        \]
        Eine Sprache $L \subseteq \Sigma^*$ heißt \alert{kontextfrei} gdw es eine kontextfreie Grammatik $G$ gibt mit $L = L(G)$.
    \end{definition}
\end{frame}
}

\defineUnit{induktivesprachdefinition}{%
\begin{frame}
    \frametitle{Induktive Sprachdefinition}
    \setbeamercovered{dynamic}

    \begin{block}{Induktive Sprachdefinition}
        Die \alert{induktive Definition} zu einer Grammatik $G$ ergibt sich direkt aus ihren Produktionen. Dabei werden kleinere Worte zu größeren Worten \alert{zusammengesetzt}, die Definition erfolgt \structure{bottom-up}.
    \end{block}

    \vfill

    \begin{example}
        Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$:

        \begin{align*}
            1 &\in L_G(S) \\
            u \in L_G(S) \quad \Longrightarrow \quad 0\alert{u}1 &\in L_G(S) \\
            u \in L_G(S) \quad \Longrightarrow \quad \alert{u}11 &\in L_G(S)
        \end{align*}

        Also z.B:

        \[
            1 \in L_G(S) \Longrightarrow 0\alert{1}1 \in L_G(S) \Longrightarrow \alert{011}11 \in L_G(S)
        \]
    \end{example}
\end{frame}
}

\defineUnit{eindeutigkeit}{%
\begin{frame}
    \frametitle{Eindeutigkeit}

    \begin{definition}[kontextfreie Linksableitung]
        Eine Ableitung
        \begin{align}
            S \to^* \structure{x}\alert{A}z \to \structure{x}\alert{\beta}z \to^* w
        \end{align}
        heißt (kontextfreie) \structure{Linksableitung}, wenn für jede Anwendung jeder Produktion $\alert{A \to \beta}$ gilt, dass in \structure{$x$} kein Nichtterminal vorkommt.
    \end{definition}

    \vfill

    \begin{definition}[Eindeutigkeit]
        \begin{itemize}
            \item Eine Grammatik heißt \structure{eindeutig}, wenn es für jedes Wort genau eine Linksableitung gibt.
            \item Eine Sprache heißt \structure{eindeutig}, wenn es für sie eine eindeutige Grammatik gibt.
        \end{itemize}
    \end{definition}
\end{frame}
}

\defineUnit{cnf}{%
\begin{frame}
    \frametitle{CNF}
    \setbeamercovered{dynamic}

    \begin{definition}[Chomsky-Normalform]
        Eine kontextfreie Grammatik ist in \structure{Chomsky-Normalform} (CNF) genau dann wenn alle Produktionen die Form
        \[
            A \rightarrow \alert{a} \quad \text{oder} \quad A \rightarrow \alert{BC}
        \]
        haben.
    \end{definition}

    \vfill

    \begin{theorem}
        Zu \alert{jeder} CFG $G$ existiert eine CFG $G'$ in Chomsky-Normalform mit
        \[
            L(G') = L(G) \alert{\setminus \left\{ \epsilon \right\}}
        \]
    \end{theorem}
\end{frame}
}

\defineUnit{cnfkonstruktion}{%
\begin{frame}
    \frametitle{CNF Konstruktion}
    \setbeamercovered{dynamic}

    \begin{block}{CNF Konstruktion}
        Sei $G = (V, \Sigma, P, S)$ eine CFG.
        \begin{enumerate}
            \item<1,2-> Eliminiere \alert{$\epsilon$-Produktionen}
            \item<1,3-> Eliminiere \alert{Kettenproduktionen}
            \item<1,4-> \alert{Ersetze Terminale} durch Nichtterminale
            \item<1,5-> \alert{Verkürze Ketten} von Nichtterminalen der Länge $\geq 3$
        \end{enumerate}
    \end{block}

    \vspace{1em}

    \only<2> {
        Sind \alert{$B \rightarrow \epsilon$} und \alert{$A \rightarrow \alpha B \beta$} in $P$, dann füge \alert{$A \rightarrow \alpha \beta$} hinzu. Entferne danach alle $\epsilon$-Produktionen.
        \begin{align*}
            S &\rightarrow Ab, \quad A \rightarrow aAA \mid \epsilon \\
            \intertext{wird zu:}
            S &\rightarrow \alert{Ab \mid b} \\
            A &\rightarrow \alert{aAA \mid aA \mid a}
        \end{align*}
    }

    \only<3> {
        Sind \alert{$A \rightarrow B$} und \alert{$B \rightarrow \alpha$} in $P$, dann füge \alert{$A \rightarrow \alpha$} hinzu. Entferne danach alle Kettenproduktionen und unerreichbaren Symbole.
        \begin{align*}
            S &\rightarrow A, \quad A \rightarrow a \mid B, \quad B \rightarrow bS \\
            \intertext{wird zu:}
            A &\rightarrow \alert{a \mid bS} \\
            S &\rightarrow \alert{a \mid bS}
        \end{align*}
    }

    \only<4> {
        Ersetze jedes \alert{$a \in \Sigma$} in einer rechten Seite \alert{länger als $1$} durch ein neues Nichtterminal.
        \begin{align*}
            S &\rightarrow aa \mid Bb \mid b, \quad B \rightarrow \ldots \\
            \intertext{wird zu:}
            S &\rightarrow \alert{X_aX_a \mid BX_b \mid b} \\
            X_a &\rightarrow \alert{a}, \quad X_b \rightarrow \alert{b}
        \end{align*}
    }

    \only<5> {
        Ersetze jede Produktion der Form $A \rightarrow B_1B_2\ldots B_k$ durch neue Nichtterminale mit Produktionen der Länge $2$.
        \begin{align*}
            S &\rightarrow X_aX_bBX_a, \quad X_a \rightarrow a, \quad X_b \rightarrow b, \quad B \rightarrow \ldots \\
            \intertext{wird zu:}
            S &\rightarrow \alert{X_aT_1} \\
            T_1 &\rightarrow \alert{X_bT_2}, \quad T_2 \rightarrow \alert{BX_a} \\
        \end{align*}
    }
\end{frame}
}

\defineUnit{nuetzlichessymbol}{%
\begin{frame}
    \frametitle{Eigenschaften von Symbolen}
    \setbeamercovered{dynamic}

    \begin{definition}
        Sei $G = (V, \Sigma, P, S)$ eine CFG. \\
        Ein Symbol $X \in V \cup \Sigma$ ist
        \begin{description}
            \item[nützlich] es gibt $S \rightarrow_G^* w \in \Sigma^*$ in der X \alert{vorkommt}
            \item[erzeugend] es gibt $\alert{X} \rightarrow_G^* w \in \Sigma^*$
            \item[erreichbar] es gibt $S \rightarrow_G^* \alpha \alert{X} \beta$
        \end{description}
    \end{definition}

    \vfill

    \begin{theorem}
        Nützliche Symbole \alert{sind} erzeugend und erreichbar. Aber \alert{nicht} notwendigerweise umgekehrt.
        \[
            S \rightarrow AB \mid a, \quad A \rightarrow b
        \]
    \end{theorem}
\end{frame}
}

\defineUnit{cfpl}{%
\begin{frame}
    \frametitle{Pumping Lemma für CFLs}
    \setbeamercovered{dynamic}

    \begin{theorem}[Pumping Lemma für kontextfreie Sprachen]
        Sei $L \subseteq \Sigma^*$ kontextfrei.\\
        Dann gibt es ein $n > 0$, so dass sich \alert{jedes} $z \in L$ mit $|z| \geq n$ so in \alert{$z = uvwxy$} zerlegen lässt, dass
        \begin{itemize}
            \item $vx \alert{\neq \epsilon}$
            \item $|vwx| \alert{\leq n}$
            \item $\forall i \alert{\geq 0}. uv^iwx^iy \in L$
        \end{itemize}
    \end{theorem}

    \vfill

    \vspace{1.5em}
    \begin{center}
        \begin{columns}
            \begin{column}{.4\textwidth}
                \begin{tikzpicture}
                    \coordinate (outer) at (2, 2.4);
                    \coordinate (middle) at (2.2, 1.2);
                    \coordinate (inner) at (2.2, 0.6);
                    % outer
                    \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0);
                    % middle
                    \draw[fill=tumgreen!40] (1.2, 0) -- (1.7, 0) -- (inner) -- (2.7, 0) -- (3.2, 0) -- (middle) -- (1.2, 0);
                    % inner
                    \draw[fill=tumblue!40] (1.7, 0) -- (inner) -- (2.7, 0) -- (1.7, 0);

                    % path
                    \draw[dashed, thick] (outer) -- (middle) -- (inner);
                    \draw[fill] (outer) circle (1pt);
                    \draw[fill] (middle) circle (1pt);
                    \draw[fill] (inner) circle (1pt);

                    % nodes
                    \node[below] at (0.6, 0) {$u$};
                    \node[below] at (1.45, 0) {$v$};
                    \node[below] at (2.2, 0) {$w$};
                    \node[below] at (2.95, 0) {$x$};
                    \node[below] at (3.6, 0) {$y$};

                    \node[right] at (middle) {$A$};
                    \node[right] at (inner) {$A$};

                    \node at (2, 3.4) {$S \to^* uAy \to^* uvAxy \to^* uvwxy$};
                \end{tikzpicture}
            \end{column}
            \begin{column}{.4\textwidth}
                \begin{tikzpicture}
                    \coordinate (outer) at (2, 2.4);
                    \coordinate (middle) at (2.2, 1.2);
                    \coordinate (inner) at (2.2, 0.6);
                    % outer
                    \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0);
                    % inner
                    \draw[fill=tumblue!40] (1.7, 0.6) -- (middle) -- (2.7, 0.6) -- (1.7, 0.6);

                    % path
                    \draw[dashed, thick] (outer) -- (middle);
                    \draw[fill] (outer) circle (1pt);
                    \draw[fill] (middle) circle (1pt);

                    % nodes
                    \node[below] at (0.6, 0) {$u$};
                    \node[below] at (2.2, 0) {$w$};
                    \node[below] at (3.6, 0) {$y$};

                    \node[right] at (middle) {$A$};

                    \node at (2, 3.4) {$S \to^* uAy  \to^* uwy$};
                \end{tikzpicture}
            \end{column}
        \end{columns}
    \end{center}
\end{frame}
}

\defineUnit{ogden}{%
\begin{frame}
    \frametitle{Ogden Lemma für kontextfreie Sprachen}
    \setbeamercovered{dynamic}

    \begin{theorem}[Ogden Lemma für kontextfreie Sprachen]
        Sei $L \subseteq \Sigma^*$ kontextfrei.\\
        Dann gibt es ein $n > 0$, so dass für \alert{jedes} $z \in L$ mit $|z| \geq n$ gilt:\\
        Für \alert{jede} Markierung $M$ von \alert{mindestens $n$} Buchstaben in $z$ gibt es eine Zerlegung $z = uvwxy$ mit
        \begin{itemize}
            \item $|vx|_M \alert{\geq 1}$
            \item $|vwx|_M \alert{\leq n}$
            \item $\forall i \alert{\geq 0}. uv^iwx^iy \in L$
        \end{itemize}
    \end{theorem}

    \hfill

    \begin{example}[Markierung]
        Sei $w = abaabaaa$ ein Wort. Dann ist
        \begin{align}
            w = a\structure{ba}a\structure{b}aaa
        \end{align}
        eine Markierung mit $|w|_M = 3$.
    \end{example}
\end{frame}
}

\defineUnit{cyk}{%
\begin{frame}
    \frametitle{CYK}
    \setbeamercovered{dynamic}

    \begin{definition}[Cocke-Younger-Kasami-Algorithmus]
        Der \structure{CYK-Algorithmus} entscheidet das Wortproblem für kontextfreie Grammatiken in Chomsky-Normalform in $\Oh(n^3)$. \\
        Gegeben eine \alert{Grammatik} $G = (V, \Sigma, P, S)$ in CNF und ein \alert{Wort} $w = a_1 \ldots a_n \in \Sigma^*$.
        Mit \[ V_{ij} := \left\{ A \in V \mid A \rightarrow_G^* \alert{a_i \ldots a_j} \right\}\]
        ist \[ w \in L(G) \Leftrightarrow S \in V_{\alert{1n}} \]
    \end{definition}

    \begin{align*}
        V_{ii} &= \left\{ A \in V \mid (A \rightarrow a_i) \in P \right\} \\
        V_{ij} &= \left\{ A \in V \mid \exists k, B \in V_{ik}, C \in V_{k+1,j} \;.\; (A \rightarrow BC) \in P \right\}
    \end{align*}
\end{frame}
}

\defineUnit{cykbeispiel}{%
\begin{frame}
    \frametitle{CYK}
    \setbeamercovered{dynamic}

    \begin{block}{CYK-Algorithmus}
        Kombiniere \alert{Teilwörter} zum ganzen Wort, wenn möglich.
        \begin{enumerate}
            \item Initialisiere mit den \alert{$V_{ii}$}.
            \item<3-5> Befülle die Tabelle von unten nach oben.
        \end{enumerate}
    \end{block}

    \[ S \rightarrow AB \mid BC, \quad A \rightarrow BA \mid a, \quad B \rightarrow CC \mid b, \quad C \rightarrow AB \mid a \]
    \vspace{2em}
    \begin{center}
        \extrarowsep=5pt
        \begin{tabu}to .8\textwidth{r|X[c]|X[c]|X[c]|X[c]|}
            \tabucline{2-2}
            4 & \alt<-4>{}{$S,\ldots$} \\ \tabucline{2-3}
            3 & \alt<-3>{}{$\emptyset$} & \alt<-3>{}{$S, A, C$} \\ \tabucline{2-4}
            2 & \alt<-2>{}{$A,S$} & \alt<-2>{}{$B$} & \alt<-2>{}{$B$} \\ \tabucline{2-5}
            1 & \alt<-1>{}{$B$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} \\ \tabucline{2-5}
            \multicolumn{1}{r}{} & \multicolumn{1}{c}{\alert{b}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} \\
        \end{tabu}
    \end{center}
\end{frame}
}

\defineUnit{greibach}{%
\begin{frame}
    \frametitle{Greibach-Normalform}

    \begin{definition}[Greibach-Normalform]
        Eine kontextfreie Grammatik ist in \structure{Greibach-Normalform} (GNF) genau dann wenn alle Produktionen außer $S \to \epsilon$ die Form
        \[
            A \rightarrow \alert{a\alpha} \quad \text{mit} \quad a \in \Sigma, \alpha \in V^*
        \]
        haben.
    \end{definition}

    \vfill

    \begin{theorem}
        Zu \alert{jeder} CFG $G$ existiert eine CFG $G'$ in Greibach-Normalform mit
        \[
            L(G') = L(G)
        \]
    \end{theorem}
\end{frame}

\begin{frame}
    \frametitle{Einsetzen von Produktionen}

    \begin{theorem}[Einsetzen von Produktionen]
        Enthält eine CFG die Produktionen
        \begin{align}
            A &\to \alpha_1 \structure{B} \alpha_2\\
            \structure{B} &\to \alert{\beta_1} \mid \dots \mid \alert{\beta_k}
            \intertext{so ändert sich die erzeugte Sprache nicht, wenn man $B$ in $A$ \structure{einsetzt}.}
            A &\to \alpha_1 \alert{\beta_1} \alpha_2 \mid \dots \mid \alpha_1 \alert{\beta_k} \alpha_2
        \end{align}
    \end{theorem}

    \vfill

    \begin{example}
        Die Grammatik
        \begin{align}
            S &\to a \mid a\structure{B}c \\
            \structure{B} &\to \alert{b} \mid \alert{bS}
            \intertext{ist äquivalent zur Grammatik}
            S &\to a \mid a\alert{b}c \mid a\alert{bS}c
        \end{align}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Linksrekursive Produktionen}

    \begin{definition}[Linksrekursive Produktion]
        Man nennt eine Produktion \structure{linksrekursiv}, wenn sie die Form
        \[
            \structure{A} \to \structure{A}\alpha_1 \mid \dots \mid \structure{A}\alpha_k \mid \beta_1 \mid \dots \mid \beta_l \quad \text{mit} \quad \alpha_i, \beta_i \in \left( V \cup \Sigma \right)^+
        \]
        hat, wobei die $\beta_i$ nicht mit $A$ beginnen.
    \end{definition}

    \vfill

    \begin{theorem}[Ersetzen von linksrekursiven Produktionen]
        Sei $A$ eine linksrekursive Produktion einer CFG.\\
        Dann ändert sich die erzeugte Sprache nicht, wenn wir $A$ \structure{ersetzen} durch
        \begin{align}
            \structure{A} &\to \beta_1 \mid \dots \mid \beta_l \mid \beta_1 \alert{B} \mid \dots \mid \beta_l \alert{B}\\
            \alert{B} &\to \alpha_1 \mid \dots \mid \alpha_k \mid \alpha_1 \alert{B} \mid \dots \mid \alpha_k \alert{B}
        \end{align}
        \alert{$B$} ist niemals linksrekursiv.
    \end{theorem}
\end{frame}
}

\defineUnit{greibachkonstruktion}{%
\begin{frame}
    \frametitle{GNF Konstruktion}

    \begin{block}{GNF Konstruktion}
        Sei $G = (V, \Sigma, P, S)$ eine CFG.
        \begin{enumerate}
            \item<1,2-> \alert{Nummeriere} Nichtterminale
            \item<1,3-> Mache Prduktionen \alert{aufsteigend} und \alert{nicht rekursiv}
            \item<1,5-> \alert{Setze} Produktionen absteigend \alert{ein}
        \end{enumerate}
    \end{block}

    \vspace{1em}

    \only<2> {
        Benenne alle Nichtterminale \structure{beliebig} um in $A_1, \dots, A_{\abs{V}}$.
        \begin{align}
            S &\rightarrow Ab, \quad A \rightarrow aAS \mid \epsilon \\
            \intertext{wird zu}
            A_1 &\to A_2b\\
            A_2 &\to aA_2A_1
        \end{align}
    }

    \only<3,4> {
        Betrachte alle Produktionen $A_l \to \dots$ in \structure{aufsteigender Reihenfolge}.\\
        \begin{itemize}
            \item Existieren Produktionen der Form $A_l \to \structure{A_r}\alpha$ mit \alert{$r < l$}, dann setze \structure{$A_r$} in $A_l$ ein.
                \only<3> {
                    \begin{align}
                        A_1 &\to A_2 \mid a \mid b \\
                        A_2 &\to \structure{A_1}A_1
                        \intertext{wird zu}
                        A_1 &\to A_2 \mid a \mid b\\
                        A_2 &\to \structure{A_2}A_1 \mid \structure{a}A_1 \mid \structure{b}A_1
                    \end{align}
                }
            \item Entferne danach alle \structure{linksrekursiven} $A_l$-Produktionen.
                \only<4> {
                    \begin{align}
                        A_2 &\to A_2\structure{A_1} \mid \alert{aA_1} \mid \alert{bA_1}
                        \intertext{wird zu}
                        A_2 &\to \alert{aA_1} \mid \alert{bA_1} \mid \alert{aA_1}A_3 \mid \alert{bA_1}A_3\\
                        A_3 &\to \structure{A_1} \mid \structure{A_1}A_3
                    \end{align}
                }
        \end{itemize}
    }

    \only<5> {
        Betrachte alle Produktionen $A_l \to \dots$ in \structure{absteigender Reihenfolge}.\\
        \begin{itemize}
            \item Existieren Produktionen der Form $A_l \to \structure{A_r}\alpha$ mit \alert{$r > l$}, dann setze \structure{$A_r$} in $A_l$ ein.
                \begin{align}
                        A_1 &\to a \mid b \mid \structure{A_2} \\
                        A_2 &\to aA_1 \mid bA_1 \mid aA_1A_3 \mid bA_1A_3\\
                        A_3 &\to bA_3 \mid c
                        \intertext{$A_1$ wird zu}
                        A_1 &\to a \mid b \mid \structure{aA_1} \mid \structure{bA_1} \mid \structure{aA_1A_3} \mid \structure{bA_1A_3}
                \end{align}
        \end{itemize}

    }
\end{frame}
}

\defineUnit{pda}{%
\begin{frame}
    \frametitle{Kellerautomaten}
    \setbeamercovered{dynamic}

    \begin{definition}[Kellerautomat]
        Ein \structure{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem
        \begin{itemize}
            \item endlichen Menge von \structure{Zuständen} $Q$
            \item endlichen \structure{Eingabealphabet} $\Sigma$
            \item endlichen \structure{Kelleralphabet} $\Gamma$
            \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$
            \item \structure{Startzustand} $q_0 \in Q$
            \item \structure{Kellerinitialisierung} $Z_0 \in \Gamma$
            \item Menge von \structure{Endzuständen} $F \subseteq Q$
        \end{itemize}
    \end{definition}

    \vfill

    \begin{center}
        \begin{tikzpicture}[automaton, node distance=4cm]
            \node[state] (q0) {$q_i$};
            \node[state] (q1) [right of = q0] {$q_j$};

            \draw[every edge] (q0) edge node {$a, X/\gamma$} (q1);
        \end{tikzpicture}
    \end{center}
\end{frame}
}

\defineUnit{pdaakzeptanz}{%
\begin{frame}
    \frametitle{Kellerautomaten}
    \setbeamercovered{dynamic}

    \begin{definition}[Kellerautomat]
        Ein \structure{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem
        \begin{itemize}
            \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$
        \end{itemize}
    \end{definition}

    \vfill

    \begin{definition}[Akzeptanz]
        Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \structure{mit Endzustand} gdw
        \[ \exists \alert{f \in F}, \gamma \in \Gamma^*.(q_0, w, Z_0) \rightarrow_P^* (\alert{f}, \epsilon, \gamma) \]
        Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \structure{mit leerem Keller} gdw
        \[ \exists q \in Q.(q_0, w, Z_0) \rightarrow_P^* (q, \epsilon, \alert{\epsilon}) \]
    \end{definition}
\end{frame}
}

\defineUnit{pdabeispiel}{%
\begin{frame}
    \frametitle{Kellerautomaten}
    \setbeamercovered{dynamic}

    \begin{definition}[Kellerautomat]
        Ein \structure{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem
        \begin{itemize}

            \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$
        \end{itemize}
    \end{definition}

    \vfill

    \begin{example}[]
        PDA akzeptierend \alert{mit leerem Keller} zu $L = \left\{ a^nb^n \mid n \in \N_0 \right\}$.

        \bigskip
        \centering
        \begin{tikzpicture}[automaton]

            \node[state, initial] (q0) {$q_0$};
            \node[state] (q1) [right of = q0] {$q_1$};
            \node[state] (q2) [right of = q1] {$q_2$};

            \draw[->] (q0) edge [loop above] node {$\epsilon, Z_0/\epsilon$} (q0);

            \draw[->] (q0) edge node {$a, Z_0/AZ_0$} (q1);
            \draw[->] (q1) edge node {$\epsilon, A/A$} (q2);

            \draw[->] (q1) edge [loop above] node {$a, */A*$} (q1);

            \draw[->] (q2) edge [loop above] node {$b, A/\epsilon$} (q2);
            \draw[->] (q2) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q2);
        \end{tikzpicture}
    \end{example}
\end{frame}
}

\defineUnit{kontextfreiesprachen}{%
\begin{frame}
    \frametitle{Kontextfreie Sprachen}
    \setbeamercovered{dynamic}

    \begin{center}
        \begin{tikzpicture}[node distance=3cm]
            \node (CFG) {CFG};
            \node (CNF) [right of = CFG] {CNF};
            \node (PDAe) [right of = CNF] {PDA$_\epsilon$};
            \node (PDAf) [right of = PDAe] {PDA$_F$};

            \draw [every edge, <->] (CFG) -- (CNF);
            \draw [every edge, <->] (CNF) -- (PDAe);
            \draw [every edge, <->] (PDAe) -- (PDAf);
        \end{tikzpicture}
    \end{center}

    \vfill

    \begin{itemize}
        \item \alert{Abschlusseigenschaften}
    \end{itemize}
    \begin{table}
        \begin{tabu}to \textwidth{X[c]|ccccc}
            & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{}
            REG & ja & ja & ja & ja & ja\\
            CFL & nein & ja & nein & ja & ja
        \end{tabu}
    \end{table}

    \begin{itemize}
        \item \alert{Entscheidbarkeit}
    \end{itemize}
    \begin{table}
        \begin{tabu}to \textwidth{X[c]|cccc}
            & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{}
            DFA & $\Oh(n)$ & ja & ja & ja \\
            CFG & $\Oh(n^3)$ & ja & nein & nein
        \end{tabu}
    \end{table}
\end{frame}
}