\input{preamble.tex}

\title{Übung 5: Kontextfreie Sprachen}
\subtitle{Theoretische Informatik Sommersemester 2013}
\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}

\begin{document}

\begin{frame}
    \titlepage
\end{frame}

\begin{frame}
    \frametitle{Grammatiken}
    \setbeamercovered{dynamic}

    \begin{definition}[Kontextfreie Grammatik]
        Eine \alert{kontextfreie 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 V \times \left( V \cup \Sigma \right)^*$
            \item[S] ein \alert{Startsymbol}
        \end{description}
    \end{definition}

    \begin{example}[Vorbereitung 3]
        $\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.
        \pause
        \[
            S \rightarrow 0S1 \mid S11 \mid 1
        \]
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Ableitungsrelation}
    \setbeamercovered{dynamic}

    \begin{definition}[Ableitungsrelation]
        Eine CFG $G$ induziert eine \alert{Ableitungsrelation} $\rightarrow_G$ auf Wörtern über $V \cup \Sigma$:
        \[
            \alpha \rightarrow_G \beta
        \]
        gdw es eine Regel $A \rightarrow \gamma$ in $P$ mit Wörtern $\alpha_1, \alpha_2$ gibt, so dass
        \[
            \alpha = \alpha_1\alert{A}\alpha_2 \quad \text{und} \quad \beta = \alpha_1 \alert{\gamma} \alpha_2
        \]
    \end{definition}

    \begin{example}[Vorbereitung 3]
        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 \\
            \Rightarrow S &\rightarrow_G^* 0011111
        \end{align*}
    \end{example}
\end{frame}

\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}

\begin{frame}
    \frametitle{Induktive Sprachdefinition}
    \setbeamercovered{dynamic}

    \begin{block}{Induktive Sprachdefinition}
        Die \alert{induktive Definition} ($\Longrightarrow$) erzeugt Wörter \alert{bottom-up}, setzt also kleine Wörter zu größeren zusammen.
    \end{block}

    \begin{example}[Vorbereitung 3]
        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}0 \in L_G(S) \Longrightarrow \alert{010}11 \in L_G(S)
        \]
    \end{example}
\end{frame}

\end{document}