\input{preamble.tex}

\title{Übung 8: Turingmaschinen}
\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{Kellerautomat}
    \setbeamercovered{dynamic}

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

            \item \alert{Ü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 \right\}$.

        \centering
        \begin{tikzpicture}[automaton]

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

            \draw[->] (q0) edge [bend left] node {$\epsilon, A/A$} (q1);
            \draw[->] (q0) edge [bend right] node [below] {$\epsilon, Z_0/Z_0$} (q1);

            \draw[->] (q0) edge [loop above] node {$a, Z_0/AZ_0$} (q0);
            \draw[->] (q0) edge [loop below] node {$a, A/AA$} (q0);

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

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

    \begin{definition}[Turingmaschine]
        Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
        \begin{itemize}
            \item endlichen Menge von \alert{Zuständen} $Q$
            \item endlichen \alert{Eingabealphabet} $\Sigma$
            \item endlichen \alert{Bandalphabet} $\Gamma$ mit $\Sigma \subset \Gamma$
            \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
            \item \alert{Startzustand} $q_0 \in Q$
            \item \alert{Leerzeichen} $\square \in \Gamma \setminus \Sigma$
            \item Menge von \alert{Endzuständen} $F \subseteq Q$
        \end{itemize}
    \end{definition}
\end{frame}

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

    \begin{definition}[Turingmaschine]
        Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
        \begin{itemize}
            \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
        \end{itemize}
    \end{definition}

    \vfill

    \begin{center}
        \begin{tikzpicture}
            % Tape
            \begin{scope}[start chain, node distance=0]
                \node[on chain] {\ldots};
                \node[tape] {$\square$};
                \node[tape] (l) {$\square$};
                \node[tape] {$0$};
                \node[tape] {$1$};
                \node<1>[tape, active] (a){$0$};
                \node<2>[tape] (a){$1$};
                \node<1>[tape] (b){$0$};
                \node<2>[tape, active] (b){$0$};
                \node[tape] {$\square$};
                \node[on chain] {\ldots};
            \end{scope}

            % Head
            \node<1> [head,yshift=-4mm] at (a.south) (head) {$q_0$};
            \node<2> [head,yshift=-4mm] at (b.south) (head) {$q_1$};

            % Machine
            \node[machine, below=1.5cm of l] (machine) {Programm};
            \draw[every edge] (machine) .. controls (3.5, -2) .. (head.south);

            % Example-Transition
            \node[yshift=5mm] at (current bounding box.north) {$\delta(q_0, 0) = (q_1, 1, R)$};
        \end{tikzpicture}
    \end{center}
\end{frame}

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

    \begin{definition}[Konfiguration]
        Eine \alert{Konfiguration} ist ein Tripel $(\alpha, q, \beta) \in \Gamma^* \times Q \times \Gamma^*$. \\
        Dies modelliert eine TM mit:
        \begin{itemize}
            \item \alert{Bandinhalt} $\ldots\square\alpha\beta\square\ldots$
            \item \alert{Zustand} $q$
            \item Kopf auf dem \alert{ersten Zeichen} von $\beta\square$
        \end{itemize}
        Die \alert{Startkonfiguration} bei Eingabe $w \in \Sigma^*$ ist $(\epsilon, q_0, w)$.
    \end{definition}

    \vfill

    \only<1> {
        \begin{center}
            \begin{tikzpicture}
            % Tape
                \begin{scope}[start chain, node distance=0]
                    \node[on chain] {\ldots};
                    \node[tape] {$\square$};
                    \node[tape] (l) {$\square$};
                    \node[tape] {$0$};
                    \node[tape] {$1$};
                    \node[tape] (a){$1$};
                    \node[tape, active] (b){$0$};
                    \node[tape] {$\square$};
                    \node[on chain] {\ldots};
                \end{scope}

            % Head
                \node [head,yshift=-4mm] at (b.south) (head) {$q_1$};

            % Machine
                \node[below=1.5cm of l] (machine) {};
                \draw[every edge, dashed] (machine) .. controls (3.5, -2) .. (head.south);

            % Example-Transition
                \node[yshift=5mm] at (current bounding box.north) {$(011,q_1,0)$};
            \end{tikzpicture}
        \end{center}
    }

    \only<2> {
        \begin{definition}[Akzeptanz]
            Eine TM $M$ \alert{akzeptiert} die Sprache
            \[ L(M) = \left\{ w \in \Sigma^* \mid \exists \alert{f \in F}, \alpha, \beta \in \Gamma^* . (\epsilon, q_0, w) \rightarrow_M^* (\alpha, \alert{f}, \beta) \right\} \]
        \end{definition}
    }
\end{frame}

\begin{frame}
    \frametitle{Nichtdeterministische TM}
    \setbeamercovered{dynamic}

    \begin{definition}[Nichtdeterministische Turingmaschine]
        Eine \alert{nichtdeterministische} Turingmaschine (TM) ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
        \begin{itemize}
            \item \ldots
            \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to \mathcal{P} \left( Q \times \Gamma \times \left\{ L, R, N \right\} \right)$
            \item \ldots
        \end{itemize}
    \end{definition}

    \vfill

    \begin{theorem}
        Zu jeder nichtdeterministischen TM $N$ gibt es eine deterministische TM $M$ mit \alert{$L(N) = L(M)$}.
    \end{theorem}
\end{frame}

\end{document}