\documentclass[compress, german, t]{beamer}

\usepackage[ngerman,english]{babel}
\uselanguage{German}
\languagepath{German}

\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}

\usepackage{helvet}
\usepackage{url}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{automata}
\usetikzlibrary{calc}
\usetikzlibrary{shapes.geometric}
\usetikzlibrary{positioning}
\usepackage{tabu}

\usepackage{beamerthemeLEA2}

\newcommand{\N}       {\mathbb{N}}          % natürliche Zahlen
\newcommand{\Z}       {\mathbb{Z}}          % ganze Zahlen
\newcommand{\R}       {\mathbb{R}}          % reelle Zahlen
\newcommand{\Prob}    {\mathrm{P}}          % Wahrscheinlichkeit
\newcommand{\Oh}      {\mathcal{O}}         % O-Notation (Landau-Symbole)
\newcommand{\mycite}[1]{\textcolor{tumgreen}{[#1]}}

\tikzstyle{every edge} = [draw,very thick,->,>=latex]
\tikzstyle{every state} = [circle,thick,draw,fill=tumblue!10]
\tikzstyle{automaton} = [shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
\tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\LARGE]

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