# HG changeset patch # User Markus Kaiser # Date 1371506362 -7200 # Node ID 20168f32b94e89c56164d95b518a34b2395ea4a1 # Parent 90ffda7e20c70cb2caafb0b7cfe44c25ef3d2613 ue08 notes diff -r 90ffda7e20c7 -r 20168f32b94e notes/tex/preamble.tex --- a/notes/tex/preamble.tex Tue Jun 11 16:21:06 2013 +0200 +++ b/notes/tex/preamble.tex Mon Jun 17 23:59:22 2013 +0200 @@ -15,8 +15,9 @@ \usepackage{pgfplots} \usetikzlibrary{automata} \usetikzlibrary{calc} -\usetikzlibrary{shapes.geometric} +\usetikzlibrary{shapes} \usetikzlibrary{positioning} +\usetikzlibrary{chains} \usepackage{tabu} \usepackage{beamerthemeLEA2} @@ -32,3 +33,8 @@ \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] + +\tikzstyle{tape} = [on chain, draw, rectangle, minimum size = 6mm, fill=tumblue!10] +\tikzstyle{active} = [fill=tumred!10] +\tikzstyle{head} = [arrow box, draw, minimum size=5mm, arrow box arrows={east:.25cm, west:0.25cm, north:0.2cm}, fill=tumred!10] +\tikzstyle{machine} = [rectangle, draw, minimum width=2cm, minimum height=1cm, inner sep=3mm, fill=tumgreen!10] diff -r 90ffda7e20c7 -r 20168f32b94e notes/tex/ue08_notes.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/ue08_notes.tex Mon Jun 17 23:59:22 2013 +0200 @@ -0,0 +1,184 @@ +\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 \mapsto 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 \mapsto 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 \mapsto 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 \mapsto \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} diff -r 90ffda7e20c7 -r 20168f32b94e notes/ue08_notes.pdf Binary file notes/ue08_notes.pdf has changed