Mercurial > 14ss.theoinf
changeset 1:a9275b863a0d
add old slides
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Sun, 13 Apr 2014 17:07:23 +0200 |
| parents | a177cacbb8ea |
| children | dcbc3181a802 |
| files | notes/tex/README notes/tex/automatons.tex notes/tex/beamerthemeLEA2.sty notes/tex/computation.tex notes/tex/frames.tex notes/tex/grammars.tex notes/tex/preamble.tex |
| diffstat | 7 files changed, 2365 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/README Sun Apr 13 17:07:23 2014 +0200 @@ -0,0 +1,5 @@ +To build everything, something along the lines of + latexmk -pdf -silent complete_notes.tex ue*.tex +could be used. + +See http://users.phys.psu.edu/~collins/software/latexmk-jcc/
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/automatons.tex Sun Apr 13 17:07:23 2014 +0200 @@ -0,0 +1,682 @@ +\defineUnit{alphabet}{% +\begin{frame} + \frametitle{Alphabet} + + \begin{definition} + \begin{itemize} + \item Ein \alert{Alphabet} $\Sigma$ ist eine endliche Menge. + \item Ein \alert{Wort} über $\Sigma$ ist eine endliche Folge von Zeichen. + \item Eine Teilmenge $L \subseteq \Sigma^*$ ist eine \alert{formale Sprache} + \end{itemize} + \end{definition} + + \vfill + + \begin{definition}[Operationen auf Sprachen] + \begin{itemize} + \item $\alert{AB} = \left\{ uv \mid u \in A \wedge v \in B \right\}$ + \item $\alert{A^n} = \left\{w_1 \ldots w_n \mid w_1 \ldots w_n \in A \right\}$,\qquad $A^0 = \{\epsilon\}$ + \item $\alert{A^*} = \bigcup_{n \in \N_0} A^n$ + \end{itemize} + \end{definition} +\end{frame} +} + +\defineUnit{dfa}{% +\begin{frame} + \frametitle{DFA} + + \begin{definition}[Deterministischer endlicher Automat] + Ein \alert{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem + \begin{itemize} + \item endlichen Menge von \alert{Zuständen} $Q$ + \item endlichen \alert{Eingabealphabet} $\Sigma$ + \item totalen \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to Q$ + \item \alert{Startzustand} $q_0 \in Q$ + \item Menge von \alert{Endzuständen} $F \subseteq Q$ + \end{itemize} + \end{definition} + + \vfill + \pause + + \begin{center} + \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] + \node[state, initial] (q0) {$q_0$}; + \node[state, accepting] (q1) [right of = q0] {$q_1$}; + \node[state] (q2) [right of = q1] {$q_2$}; + + \draw[->] (q0) edge [loop above] node {0} (q0); + \draw[->] (q2) edge [loop above] node {1} (q2); + \draw[->] (q0) edge [bend left] node {1} (q1); + \draw[->] (q1) edge [bend left] node {1} (q0); + \draw[->] (q1) edge [bend left] node {0} (q2); + \draw[->] (q2) edge [bend left] node {0} (q1); + \end{tikzpicture} + \end{center} +\end{frame} +} + +\defineUnit{nfa}{% +\begin{frame} + \frametitle{NFA} + \begin{definition}[Nicht-Deterministischer endlicher Automat] + Ein \alert{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit + \begin{itemize} + \item $Q, \Sigma, q_0, F$ wie ein DFA + \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to P(Q)$ + \end{itemize} + \end{definition} + + \vfill + \pause + + \begin{center} + \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] + \node[state, initial] (q0) {$q_0$}; + \node[state, accepting] (q1) [right of = q0] {$q_1$}; +\draw[->] (q0) edge [loop above] node {0,1} (q0); \draw[->] (q0) edge node {1} (q1); \end{tikzpicture} \end{center} \end{frame} +} + +\defineUnit{enfa}{% +\begin{frame} + \frametitle{$\epsilon$-NFA} + \begin{definition}[NFA mit $\epsilon$-Übergängen] + Ein \alert{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit + \begin{itemize} + \item $Q, \Sigma, q_0, F$ wie ein DFA + \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to P(Q)$ + \end{itemize} + \end{definition} + + \vfill + \pause + + \begin{center} + \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=30, initial text=] + \node[state] (q1) {$q_1$}; + \node[state, initial] (q0) [left of = q1] {$q_0$}; + \node[state, accepting] (q2) [right of = q1] {$q_2$}; +\draw[->] (q0) edge [red] node {$\epsilon$} (q1); \draw[->] (q1) edge [loop above] node {0,1} (q1); \draw[->] (q1) edge node {1} (q2); \draw[->] (q0) edge [bend right, red] node {$\epsilon$} (q2); \end{tikzpicture} \end{center} \end{frame} +} + +\defineUnit{endlicheautomaten}{% +\begin{frame} + \frametitle{Endliche Automaten} + \begin{block}{Übergangsfunktionen} + Die Automaten $A = (Q, \Sigma, \delta, q_0, F)$ unterscheiden sich nur durch ihre Übergangsfunktionen. + + \begin{description} + \item[DFA] $\delta : Q \times \Sigma \to Q$ + \item[NFA] $\delta : Q \times \Sigma \to \alert{P(Q)}$ + \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \to \alert{P(Q)}$ + \end{description} + \end{block} + + \vfill + + \begin{theorem} + \alert{DFA}, \alert{NFA} und \alert{$\epsilon$-NFA} sind gleich mächtig und lassen sich ineinander umwandeln. + \end{theorem} +\end{frame} +} + +\defineUnit{regex}{% +\begin{frame} + \frametitle{Reguläre Ausdrücke} + \setbeamercovered{dynamic} + + \begin{definition}[Regulärer Ausdruck] + \alert{Reguläre Ausdrücke} sind induktiv definiert + \begin{itemize} + \item \alert{$\emptyset$} ist ein regulärer Ausdruck + \item \alert{$\epsilon$} ist ein regulärer Ausdruck + \item Für alle $a \in \Sigma$ ist \alert{$a$} ein regulärer Ausdruck + \item Sind $\alpha$ und $\beta$ reguläre Ausdrücke, dann auch + \begin{description} + \item[Konkatenation] \alert{$\alpha\beta$} + \item[Veroderung] \alert{$\alpha \mid \beta$} + \item[Wiederholung] \alert{$\alpha^*$} + \end{description} + \end{itemize} + Analoge Sprachdefinition, z.b. $L(\alpha\beta) = L(\alpha)L(\beta)$ + \end{definition} + + \begin{example} + $\alpha = (0|1)^*00$ \hfill $L(\alpha) = \left\{x \mid x \text{ Binärzahl}, x \mod 4 = 0 \right\}$ + \end{example} +\end{frame} +} + +\defineUnit{automatenkonversionen}{% +\begin{frame}[c] + \frametitle{Konversionen} + \setbeamercovered{dynamic} + + \begin{center} + \begin{tikzpicture}[node distance=2cm] + \node (nfa) {NFA}; + \node (dfa) [left of=nfa] {DFA}; + \node (enfa) [right of=nfa] {$\epsilon$-NFA}; + \node (re) [below of=nfa] {RE}; + + \draw [every edge, tumred] (nfa) -- (dfa); + \draw [every edge, tumred] (enfa) -- (nfa); + \draw [every edge] (dfa) -- (re); + \draw [every edge] (nfa) -- (re); + \draw [every edge, tumred] (re) -- (enfa); + \end{tikzpicture} + \end{center} +\end{frame} +} + +\defineUnit{rezuenfa}{% +\begin{frame} + \frametitle{RE $\rightarrow$ $\epsilon$-NFA} + \setbeamercovered{dynamic} + + \begin{block}{Idee (Kleene)} + Für einen Ausdruck \alert{$\gamma$} wird rekursiv mit struktureller Induktion ein $\epsilon$-NFA konstruiert. + \end{block} + + \begin{tabu} to \linewidth {XXX} + \alert{$\gamma = \emptyset$} & \alert{$\gamma = \epsilon$} & \alert{$\gamma = a \in \Sigma$} \\ + \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)] + \node[state, initial] () {}; + \end{tikzpicture} & + + \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)] + \node[state, initial, accepting] () {}; + \end{tikzpicture} & + + \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)] + \node[state, initial] (i) {}; + \node[state, accepting] (j) [right of=i] {}; + + \draw[->] (i) edge node {$a$} (j); + \end{tikzpicture} \\ + \vspace{2em} + \alert{$\gamma = \alpha\beta$} \\ + \multicolumn3{c}{ + \begin{tikzpicture}[automaton, small] + \draw[tumgreen, fill=tumgreen!20] (-0.3, 1) rectangle (1.8, -1); + \node[tumgreen] () at (0.75, -1.2) {$N_\alpha$}; + + \draw[tumgreen, fill=tumgreen!20] (3.7, 1) rectangle (5.8, -1); + \node[tumgreen] () at (4.75, -1.2) {$N_\beta$}; + + \node[state, initial] (i) at (0, 0) {}; + \node[state] (j) at (1.5, 0.5) {}; + \node[state] (k) at (1.5, -0.5) {}; + \node[state] (l) at (4, 0) {}; + \node[state, accepting] (m) at (5.5, 0) {}; + + \draw[->] (j) edge node {$\epsilon$} (l); + \draw[->] (k) edge node {$\epsilon$} (l); + \end{tikzpicture} + }\\ + \end{tabu} +\end{frame} +} + +\defineUnit{rezuenfazwei}{% +\begin{frame} + \frametitle{RE $\rightarrow$ $\epsilon$-NFA} + \setbeamercovered{dynamic} + + \begin{tabu} to \linewidth {X} + \alert{$\gamma = \alpha \mid \beta$} \\ + \centering + \begin{tikzpicture}[automaton, small] + \draw[tumgreen, fill=tumgreen!20] (2, 1.5) rectangle (4.5, 0.5); + \node[tumgreen] () at (3.25, 0.3) {$N_\alpha$}; + + \draw[tumgreen, fill=tumgreen!20] (2, -0.5) rectangle (4.5, -1.5); + \node[tumgreen] () at (3.25, -1.7) {$N_\beta$}; + + \node[state, initial] (i) at (0, 0) {}; + + \node[state] (j) at (2.5, 1) {}; + \node[state, accepting] (k) at (4, 1) {}; + \node[state] (l) at (2.5, -1) {}; + \node[state, accepting] (m) at (4, -1) {}; + + \draw[->] (i) edge node {$\epsilon$} (j); + \draw[->] (i) edge node {$\epsilon$} (l); + \end{tikzpicture} \\ + \vfill + + \alert{$\gamma = \alpha^*$} \\ + \centering + \begin{tikzpicture}[automaton, small, bend angle=70] + \draw[tumgreen, fill=tumgreen!20] (2, 1) rectangle (4.5, -1); + \node[tumgreen] () at (3.25, -1.2) {$N_\alpha$}; + + \node[state, initial, accepting] (i) at (0, 0) {}; + + \node[state] (j) at (2.5, 0) {}; + \node[state, accepting] (k) at (4, 0.5) {}; + \node[state, accepting] (m) at (4, -0.5) {}; + + \draw[->] (i) edge node {$\epsilon$} (j); + \draw[->] (k) edge [bend right] node {$\epsilon$} (j); + \draw[->] (m) edge [bend left] node[above] {$\epsilon$} (j); + \end{tikzpicture} + \end{tabu} +\end{frame} +} + +\defineUnit{enfazunfa}{% +\begin{frame} + \frametitle{$\epsilon$-NFA $\rightarrow$ NFA} + \setbeamercovered{dynamic} + + \begin{block}{Idee} + Entferne $\epsilon$-Kanten durch das Bilden von $\epsilon$-Hüllen. + \begin{enumerate} + \item<1-> Entferne \alert{unnötige Knoten}. + \item<1,3-> Für jeden \alert{Pfad} der Form $\epsilon\ldots\epsilon \alert{a} \epsilon\ldots\epsilon$ verbinde Anfangs- und Endknoten mit einer \alert{$a$}-Kante. + \item<1,4-> Entferne alle \alert{$\epsilon$-Kanten} und unerreichbare Knoten. + \item<1,5-> Wurde das leere Wort akzeptiert mache den \alert{Anfangszustand} zum Endzustand. + \end{enumerate} + \end{block} + + \vfill + + \begin{tikzpicture}[automaton, bend angle=40, node distance=2.1cm] + \useasboundingbox (-1.4,2) rectangle (9, -2); + + \node<-4>[state, initial] (q0) {$q_0$}; + \node[state] (q2) [right = 3.2cm of q0] {$q_2$}; + \node[state] (q3) [right of = q2] {$q_3$}; + \node[state, accepting] (q4) [right of = q3] {$q_4$}; + + \draw[->] (q2) edge node {$0$} (q3); + \draw[->] (q3) edge node {$1$} (q4); + + \draw<1-4>[->] (q3) edge [bend right] node [above] {$\epsilon$} (q2); + \draw[->] (q4) edge [bend right] node [above] {$1$} (q3); + \draw<1-4>[->] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4); + + \node<1>[state] (q1) [right of = q0] {$q_1$}; + \draw<1>[->] (q0) edge node {$\epsilon$} (q1); + \draw<1>[->] (q1) edge node {$1$} (q2); + + \node<2>[state, fill=tumred!20] (q1) [right of = q0] {$q_1$}; + \draw<2>[->, tumred] (q0) edge node {$\epsilon$} (q1); + \draw<2>[->, tumred] (q1) edge node {$0$} (q2); + \draw<2->[->, tumblue] (q0) edge [bend left] node {$0$} (q2); + + \draw<3,4,5>[->, tumred] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4); + \draw<3>[->, tumred] (q4) edge [bend right] node [above] {$1$} (q3); + \draw<3,4>[->, tumred] (q3) edge [bend right] node [above] {$\epsilon$} (q2); + \draw<3->[->, tumgreen] (q0) edge node {$1$} (q2); + + \draw<4->[->, tumgreen] (q2) edge [loop above] node [above] {$0$} (q2); + \draw<4->[->, tumgreen] (q3) edge [loop above] node [above] {$0$} (q3); + \draw<4->[->, tumgreen] (q0) edge [bend right=20] node [above] {$1$} (q3); + \draw<4->[->, tumgreen] (q4) edge [bend right=70] node [above] {$1$} (q2); + + \node<5>[state, initial, accepting, fill=tumgreen!20] (q0) {$q_0$}; + + \node<6->[state, initial, accepting] (q0) {$q_0$}; + \end{tikzpicture} +\end{frame} +} + +\defineUnit{nfazudfa}{% +\begin{frame} + \frametitle{NFA $\rightarrow$ DFA} + \setbeamercovered{dynamic} + + \begin{block}{Idee (Potenzmengenkonstruktion)} + Konstruiere aus einem NFA $N = (Q, \Sigma, \delta, q_0, F)$ einen DFA $D = (P(Q), \Sigma, \overline{\delta}, \{q_0\}, F_M)$ mit Zuständen aus \alert{$P(Q)$}. + + \begin{itemize} + \item $\overline{\delta}: \alert{P(Q)} \times \Sigma \to P(Q)$ \\ + \[\overline{\delta}(S, a) := \bigcup_{q \in S} \delta(q, a)\] + \item $F_M := \left\{S \subseteq Q \mid \alert{S \cap F} \neq \emptyset\right\}$ + \end{itemize} + \end{block} + + \begin{tikzpicture}[automaton, bend angle=20, node distance=2.1cm] + \useasboundingbox (-1.4,2) rectangle (9, -2); + + \node[state, initial] (q0) {$q_0$}; + \node[state, accepting] (q1) [right of = q0] {$q_1$}; + + \draw[->] (q0) edge [loop above] node {$0,1$} (q0); + \draw[->] (q0) edge node {$1$} (q1); + + \node<2->(sep) [right of = q1] {$\rightarrow$}; + + \node<2->[state, initial, inner sep=1pt] (pq0) [right of = sep] {$q_{\{0\}}$}; + + \node<3->[state, accepting, inner sep=0pt] (pq01) [right of = pq0] {$q_{\{0,1\}}$}; + \draw<3->[->] (pq0) edge [loop above] node {$0$} (pq0); + \draw<3->[->] (pq0) edge [bend left] node {$1$} (pq01); + + \draw<4->[->] (pq01) edge [loop above] node {$1$} (pq01); + \draw<4->[->] (pq01) edge [bend left] node {$0$} (pq0); + + \end{tikzpicture} +\end{frame} +} + +\defineUnit{produktautomat}{% +\begin{frame} + \frametitle{Produktautomat} + \setbeamercovered{dynamic} + + \begin{theorem} + Sind $M_1 = (Q_1, \Sigma, \delta_1, s_1, F_1)$ und $M_2 = (Q_2, \Sigma, \delta_2, s_2, F_2)$ DFAs, dann ist der \alert{Produkt-Automat} + + \begin{align*} + M &:= (\alert{Q_1 \times Q_2}, \Sigma, \delta, (s_1, s_2), F_1 \times F_2) \\ + \delta\left( (q_1, q_2), a \right) &:= \left( \alert{\delta_1}(q_1, a), \alert{\delta_2}(q_2, a) \right) + \end{align*} + + ein DFA, der $L(M_1) \cap L(M_2)$ akzeptiert. + \end{theorem} +\end{frame} +} + +\defineUnit{regexrechnen}{% +\begin{frame} + \frametitle{Nochmal Reguläre Ausdrücke} + \setbeamercovered{dynamic} + + \begin{theorem} + Die regulären Ausdrücke $\mathfrak{R}$ über einem Alphabet $\Sigma$ bilden mit Konkatenation $\circ$ und Veroderung $\mid$ einen \alert{Halbring} $\langle \mathfrak{R}, \mid, \circ, \emptyset, \epsilon \rangle$. + + \begin{itemize} + \item \alert{Assoziative} Operationen + \item Veroderung \alert{kommutativ} + \item \alert{Distributivität}: $\alpha (\beta \mid \gamma) \equiv \alpha\beta \mid \alpha\gamma$ + \item $\emptyset$ \alert{neutral} bezüglich Oder + \item $\epsilon$ \alert{neutral} bezüglich Konkatenation + \end{itemize} + \end{theorem} + + \begin{example} + \[ + 1\psi \mid 0\phi \mid \psi \equiv 0 \phi \mid (1 \mid \epsilon) \psi + \] + \end{example} +\end{frame} +} + +\defineUnit{arden}{% +\begin{frame} + \frametitle{Ardens Lemma} + \setbeamercovered{dynamic} + + \begin{theorem}[Ardens Lemma] + Sind $A$, $B$ und $X$ Sprachen mit $\epsilon \not \in A$, dann gilt + \[ + X = AX \cup B \Longrightarrow X = A^* B + \] + Speziell gilt für reguläre Ausdrücke + \[ + X \equiv \alpha X \mid \beta \Longrightarrow X \equiv \alpha^* \beta + \] + \end{theorem} + + \begin{example} + \[ + \psi \equiv 0 \psi \mid (1 \mid \epsilon) \phi \Longrightarrow \psi \equiv 0^*(1\mid \epsilon) \phi + \] + \end{example} +\end{frame} +} + +\defineUnit{nfazure}{% +\begin{frame} + \frametitle{NFA $\rightarrow$ RE} + \setbeamercovered{dynamic} + + \begin{block}{Idee} + Erzeuge ein Gleichungssystem aus allen Zuständen. + \begin{enumerate} + \item<1,2-> Ausdruck für jeden Zustand + \item<1,3-> Auflösen nach $X_0$ mit Algebra und Ardens Lemma + \end{enumerate} + \end{block} + \begin{columns}<2-> + \begin{column}[b]{.65\textwidth} + \begin{align*} + X_0 &\equiv 1X_0 \mid 0X_1 \\ + &\equiv \uncover<4->{1X_0 \mid 00^*(\epsilon \mid 1X_0)} \\ + &\equiv \uncover<4->{(1 \mid 00^*1) X_0 \mid 00^*} \\ + &\equiv \uncover<4->{(1 \mid 00^*1)^*(00^*)} \\ + \\ + X_1 &\equiv 1X_0 \mid 0X_1 \alt<3->{\mid \epsilon}{\alert{\mid \epsilon}} \\ + &\equiv \uncover<3-> {0X_1 \mid (\epsilon \mid 1 X_0)}\\ + &\equiv \uncover<3-> {\alt<-2,4->{0^*(\epsilon \mid 1X_0)}{\alert{0^*(\epsilon \mid 1X_0)}}} + \end{align*} + \end{column} + \begin{column}[t]{.35\textwidth} + \begin{tikzpicture}[automaton] + \node[state, initial] (q0) {$q_0$}; + \node[state, accepting] (q1) [below of=q0] {$q_1$}; + + \draw[->] (q0) edge [bend right] node [left] {$0$} (q1); + \draw[->] (q1) edge [bend right] node [right] {$1$} (q0); + \draw[->] (q0) edge [loop right] node {$1$} (q0); + \draw[->] (q1) edge [loop right] node {$0$} (q1); + \end{tikzpicture} + \end{column} + \end{columns} +\end{frame} +} + +\defineUnit{rpl}{% +\begin{frame} + \frametitle{Pumping Lemma} + \setbeamercovered{dynamic} + + \begin{theorem}[Pumping Lemma für reguläre Sprachen] + Sei $R \subseteq \Sigma^*$ regulär. Dann gibt es ein $n > 0$, so dass sich \alert{jedes} $z \in R$ mit $|z| \geq n$ so in $z = uvw$ zerlegen lässt, dass + \begin{itemize} + \item $v \neq \epsilon$ + \item $|uv| \alert{\leq n}$ + \item $\forall i \alert{\geq 0}. uv^iw \in R$ + \end{itemize} + \end{theorem} + + \vfill + + \begin{center} + \begin{tikzpicture}[automaton] + \node[state, initial] (q0) {}; + \node[state, fill=tumred!20] (q1) [right of=q0] {}; + \node[state, accepting] (q2) [right of=q1] {}; + + \draw[->, densely dashed] (q0) edge node {$u$} (q1); + \draw[->, tumred] (q1) edge [loop above] node {$v$} (q1); + \draw[->, densely dashed] (q1) edge node {$w$} (q2); + \end{tikzpicture} + \end{center} +\end{frame} +} + +\defineUnit{rplanwenden}{% +\begin{frame} + \frametitle{Nichtregularität beweisen} + \setbeamercovered{dynamic} + + \begin{block}{Idee} + Gegenbeispiel fürs Pumpinglemma suchen. + \[ + \alert{\forall} n \in \N_0 \alert{\exists} z \in L. |z| \geq n \ \alert{\forall} u,v,w. \ z = uvw \ \text{\alert{nicht} pumpbar} + \] + \end{block} + + \vfill + + \begin{example}<2-> + Ist $L = \left\{ a^ib^i \mid i \in \N_0 \right\}$ regulär? + \begin{enumerate} + \item \alert{Sei $n$} PL-Zahl + \item \alert{Wähle} $\alert{z} = a^nb^n$ + \item Dann ist \alert{$z = uvw$} mit \alert{$|uv| \leq n$}, hier: $v=a^k$ mit $k > 0$ + \item Dann ist $uv^0w \not \in L$ + \item Damit ist L \alert{nicht} regulär. + \end{enumerate} + \end{example} +\end{frame} +} + +\defineUnit{aequivalentezustaende}{% +\begin{frame} + \frametitle{Äquivalenzen} + \setbeamercovered{dynamic} + + \begin{definition}[Äquivalente Worte] + Jede Sprache $L \subseteq \Sigma^*$ induziert eine Äquivalenzrelation $\alert{\equiv_L \subseteq \Sigma^* \times \Sigma^*}$: + \[ + u \alert{\equiv_L} v \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{uw} \in L \Leftrightarrow \alert{vw} \in L\right) + \] + \end{definition} + + \vfill + + \pause + + \begin{definition}[Äquivalente Zustände] + Zwei Zustände im DFA $A$ sind \alert{äquivalent} wenn sie die selbe Sprache akzeptieren. + + \[ + p \alert{\equiv_A} q \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{\hat{\delta}(p, w)} \in F \Leftrightarrow \alert{\hat{\delta}(q, w)} \in F \right) + \] + \end{definition} +\end{frame} +} + +\defineUnit{unterscheidbarezustaende}{% +\begin{frame} + \frametitle{Unterscheidbare Zustände} + \setbeamercovered{dynamic} + + \begin{definition}[Unterscheidbarkeit] + Zwei Zustände sind \alert{unterscheidbar}, wenn sie unterschiedliche Sprachen akzeptieren. + \[ + p \alert{\not\equiv_A} q \Longleftrightarrow \left( \exists w \in \Sigma^*. \hat{\delta}(p, w) \alert{\in} F \wedge \hat{\delta}(q, w) \alert{\not\in} F \right) + \] + \end{definition} + + \begin{theorem} + Sind $\delta(p, a)$ und $\delta(q, a)$ unterscheidbar, dann auch $p$ und $q$. + \end{theorem} + + \pause + + \begin{tikzpicture}[automaton, bend angle=40, node distance=2.5cm] + \node[state, initial] (q0) {$q_0$}; + \node[state] (q1) [right of = q0] {$q_1$}; + \node[state] (q2) [right of = q1] {$q_2$}; + \node[state, accepting] (q3) [right of = q2] {$q_3$}; + + \draw[->] (q0) edge node {$a$} (q1); + \draw[->] (q0) edge [bend left] node {$b$} (q2); + \draw[->] (q1) edge node {$a$} (q2); + \draw[->] (q1) edge [bend right] node {$b$} (q3); + \draw[->] (q2) edge node {$a,b$} (q3); + \draw[->] (q3) edge [loop right] node {$a,b$} (q3); + + \node<3>[state, fill=tumred!35] () at (q2) {$q_2$}; + \node<3->[state, accepting, fill=tumgreen!35] () at (q3) {$q_3$}; + + \node<4>[state, fill=tumred!35] () at (q0) {$q_0$}; + \node<4>[state, fill=tumred!35] () at (q1) {$q_1$}; + \draw<4>[->, tumred] (q0) edge [bend left] node {$b$} (q2); + \draw<4>[->, tumgreen] (q1) edge [bend right] node {$b$} (q3); + \end{tikzpicture} +\end{frame} +} + +\defineUnit{quotientenautomat}{% +\begin{frame}[t] + \frametitle{DFA minimieren} + \setbeamercovered{dynamic} + + \begin{block}{Idee} + Erzeuge den \alert{Quotientenautomaten}. + \begin{enumerate} + \item Entferne alle von $q_0$ \alert{nicht erreichbaren} Zustände + \item<1, 3-> Berechne die \alert{unterscheidbaren} Zustände + \item<1, 6-> \alert{Kollabiere} die äquivalenten Zustände + \end{enumerate} + \end{block} + + \vfill + + \begin{columns}[c]<2-> + \begin{column}{.5\textwidth}<3-> + \begin{center} + \begin{tabu}to .8\textwidth{|X[c]|X[c]|X[c]|X} + \multicolumn{2}{l}{0} \\ \tabucline{1-1} + \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} & \multicolumn{2}{l}{1} \\ \tabucline{1-2} + \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} & & \multicolumn{2}{l}{2} \\ \tabucline{1-3} + \alt<-3>{}{\textcolor{tumred}{$\times$}} & \alt<-3>{}{\textcolor{tumred}{$\times$}}& \alt<-3>{} {\textcolor{tumred}{$\times$}}& 3 \\ \tabucline{1-3} + \end{tabu} + \end{center} + \end{column} + \begin{column}{.5\textwidth} + \begin{tikzpicture}[automaton, node distance=2.5cm] + \useasboundingbox (-0.5, -0.5) rectangle (2, -2); + + \node[state, initial] (q0) {$q_0$}; + \node<-5>[state] (q1) [right of = q0] {$q_1$}; + \node<-5>[state] (q2) [below of = q0] {$q_2$}; + \node<6>[state, fill=tumred!40] (q12) [right of = q0] {$q_{12}$}; + \node[state, accepting] (q3) [right of = q2] {$q_3$}; + + \draw<-5>[->] (q0) edge node {$a$} (q1); + \draw<-5>[->] (q0) edge node {$b$} (q2); + \draw<-5>[->] (q1) edge node {$a,b$} (q3); + \draw<-5>[->] (q2) edge node {$a,b$} (q3); + \draw[->] (q3) edge [loop right] node [above] {$a,b$} (q3); + + \draw<6>[->] (q12) edge node {$a,b$} (q3); + \draw<6>[->] (q0) edge node {$a,b$} (q12); + \end{tikzpicture} + \end{column} + \end{columns} +\end{frame} +} + +\defineUnit{regulaeresprachen}{% +\begin{frame} + \frametitle{Reguläre Sprachen} + \setbeamercovered{dynamic} + + \begin{center} + \begin{tikzpicture}[node distance=2cm] + \node (nfa) {NFA}; + \node (dfa) [left of=nfa] {DFA}; + \node (enfa) [right of=nfa] {$\epsilon$-NFA}; + \node (re) [below of=nfa] {RE}; + + \draw [every edge] (nfa) -- (dfa); + \draw [every edge] (enfa) -- (nfa); + \draw [every edge] (dfa) -- (re); + \draw [every edge] (nfa) -- (re); + \draw [every edge] (re) -- (enfa); + \end{tikzpicture} + \end{center} + + \vfill + + \begin{theorem} + Für eine Darstellung $D$ einer regulären Sprache ist \alert{entscheidbar}: + \vspace{1em} + \begin{description} + \item[Wortproblem] Gegeben $w$, gilt $w \in L(D)$? + \item[Leerheitsproblem] Ist $L(D) = \emptyset$? + \item[Endlichkeitsproblem] Ist $|L(D)| < \infty$? + \item[Äquivalenzproblem] Gilt $L(D_1) = L(D_2)$? + \end{description} + \end{theorem} +\end{frame} +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/beamerthemeLEA2.sty Sun Apr 13 17:07:23 2014 +0200 @@ -0,0 +1,60 @@ +\ProvidesPackage{beamerthemeLEA2} + +\xdefinecolor{tumblue} {RGB}{ 0,101,189} +\xdefinecolor{tumgreen} {RGB}{162,173, 0} +\xdefinecolor{tumred} {RGB}{229, 52, 24} +\xdefinecolor{tumivory} {RGB}{218,215,203} +\xdefinecolor{tumorange} {RGB}{227,114, 34} +\xdefinecolor{tumlightblue}{RGB}{152,198,234} + +%% shadow, font, color, outer, inner +%% normal text, alerted text, example text, structure + +\useoutertheme{split} + +\setbeamercolor{normal text}{fg=black,bg=white} +\setbeamercolor{alerted text}{fg=tumred,bg=white} +\setbeamercolor{example text}{fg=tumgreen,bg=white} +\setbeamercolor{structure}{fg=tumblue,bg=white} +\setbeamercolor{titlelike}{fg=tumblue} +\setbeamercolor{subtitle}{fg=black} +\setbeamerfont{title}{series=\bfseries} + +\setbeamertemplate{sections/subsections in toc}[square] +\setbeamertemplate{items}[square] +\setbeamertemplate{navigation symbols}[only frame symbol] + +\setbeamertemplate{blocks}[default] + +\setbeamercolor{block title} {use=normal text, fg=black,bg=tumlightblue} +\setbeamercolor{block title alerted}{use=alerted text,fg=white,bg=alerted text.fg} +\setbeamercolor{block title example}{use=example text,fg=white,bg=example text.fg} + +\setbeamercolor{block body} {parent=normal text,use=block title, bg=block title.bg!25!bg} +\setbeamercolor{block body alerted}{parent=normal text,use=block title alerted,bg=block title.bg!25!bg} +\setbeamercolor{block body example}{parent=normal text,use=block title example,bg=block title example.bg!15!bg} + +\pgfdeclareimage[height=5mm]{uni}{TU_Muenchen_Logo_Breit} +\logo{\pgfuseimage{uni}} + +\defbeamertemplate*{footline}{infolines theme}{% + \hspace*{2ex}\raisebox{1.5ex}[-1.5ex]{% + \tiny\insertframenumber{}/\inserttotalframenumber \hspace{5mm} \insertnavigation{0.8\paperwidth}}% +} + +\setbeamertemplate{frametitle}{ + \begin{beamercolorbox}[wd=80mm,leftskip=0mm]{frametitle} + \usebeamerfont*{frametitle} + \insertframetitle\hfill\parbox{10mm}{\vspace{-2mm}\insertlogo}\hspace{-2mm} + \end{beamercolorbox} + \vspace{-3mm}\textcolor{tumblue}{\noindent\rule{\textwidth}{0.4px}} +} +% hier kein Logo +\setbeamertemplate{sidebar right}{\vfill\vskip2pt\llap{\usebeamertemplate***{navigation symbols}\hskip1mm}\vskip2pt} + +\setbeamertemplate{headline}{} + +\setbeamercovered{transparent} + +% escapeinside= removed for utf8 compatibility +\lstset{numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\small, backgroundcolor=\color{tumlightblue}}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/computation.tex Sun Apr 13 17:07:23 2014 +0200 @@ -0,0 +1,1023 @@ +\defineUnit{tmdefinition}{% +\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} +} + +\defineUnit{tmvisualisierung}{% +\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} +} + +\defineUnit{tmkonfiguration}{% +\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} +} + +\defineUnit{ndtm}{% +\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} +} + +\defineUnit{chomsky}{% +\begin{frame}[c] + \frametitle{Chomsky-Hierarchie} + \setbeamercovered{dynamic} + + \begin{center} + \begin{tikzpicture}[auto] + \tikzstyle{rect} = [thick]; + \tikzstyle{caption} = [align=left, anchor=north west]; + + \chomsky{tumblue}{}{0}{Berechenbare Funktionen}; + \chomsky{tumred}{dashed}{1}{Typ 0 - Rekursiv aufzählbar\\Turingmaschinen, $\lambda$-Kalkül}; + \chomsky{tumivory}{}{2}{Typ 1 - Kontextsensitiv\\CSG}; + \chomsky{tumorange}{}{3}{Typ 2 - Kontextfrei\\PDA, CFG}; + \chomsky{tumgreen}{}{4}{Typ 3 - Regulär\\DFA, RE}; + \end{tikzpicture} + \end{center} +\end{frame} +} + +\defineUnit{berechenbarkeit}{% +\begin{frame} + \frametitle{Berechenbarkeit} + \setbeamercovered{dynamic} + + \begin{definition}[Intuitive Berechenbarkeit] + Eine Funktion $f : \N^k \to \N$ heißt \alert{intuitiv berechenbar}, wenn es einen Algorithmus gibt, der bei Eingabe $(n_1, \ldots, n_k) \in \N^k$ + \begin{itemize} + \item nach \alert{endlich vielen Schritten} mit Ergebnis $f(n_1, \ldots, n_k)$ hält, falls $f(\ldots)$ definiert ist, + \item und \alert{nicht terminiert}, falls $f(\ldots)$ nicht definiert ist. + \end{itemize} + \end{definition} + + \vfill + + \begin{block}{Churchsche These (nicht beweisbar)} + Turing-Maschinen können genau \alert{alle} intuitiv berechenbaren Funktionen berechnen. + \end{block} +\end{frame} +} + +\defineUnit{berechenbarkeitbeispiel}{% +\begin{frame}[c] + \frametitle{Berechenbarkeit} + \setbeamercovered{dynamic} + + \begin{example}[Berechenbarkeit] + Sind die folgenden Funktionen intuitiv berechenbar? + + \begin{align*} + f_1(n) &= \begin{cases} + 1 & \text{falls $n$ prim}\\ + 0 & \text{sonst} + \end{cases} \\ + f_2(n) &= \begin{cases} + 1 & \text{falls $n$ die ersten $n$ Ziffern von $\pi$ darstellt}\\ + 0 & \text{sonst} + \end{cases} \\ + f_3(n) &= \begin{cases} + 1 & \text{falls in $\pi$ $n$ Nullen am Stück vorkommen}\\ + 0 & \text{sonst} + \end{cases} + \end{align*} + \end{example} +\end{frame} +} + +\defineUnit{pr}{% +\begin{frame} + \frametitle{Primitive Rekursion} + \setbeamercovered{dynamic} + + \begin{definition}[Basisfunktionen] + \alert{Primitiv Rekursiv} sind: + \begin{itemize} + \item Die konstante Funktion \alert{0} + \item Die \alert{Nachfolgerfunktion} $s(n) = n + 1$ + \item Die \alert{Projektionsfunktion} $\pi_i^k : \N^k \to \N, i \in [k]$ + \[ \pi_i^k(x_1, \ldots, x_k) = x_i \] + \end{itemize} + \end{definition} + + \begin{definition}[Komposition] + Sind $g$ und $h_i$ PR und $\bar{x} = (x_1, \ldots, x_n)$, dann ist auch \alert{$f$} PR: + \[ f(\bar{x}) = \alert{g(h_1(\bar{x}), \ldots, h_k(\bar{x}))} \] + \end{definition} +\end{frame} +} + +\defineUnit{prrekursion}{% +\begin{frame} + \frametitle{Primitive Rekursion} + \setbeamercovered{dynamic} + \begin{block}{Basisfunktionen und Komposition} + Schon \alert{PR} sind: + \begin{itemize} + \item Konstante: $0$ + \item Nachfolger: $s(n) = n + 1$ + \item Projektion: $\pi_i^k : \N^k \to \N$ + \item Komposition: $f(\bar{x}) = g(h_1(\bar{x}), \ldots, h_k(\bar{x}))$ + \end{itemize} + \end{block} +\begin{definition}[Primitive Rekursion] Das Schema der \alert{primitiven Rekursion} erzeugt aus $g$ und $h$ die Funktion \alert{$f$}: \begin{align*} f(0, \bar{x}) &= g(\bar{x}) \\ f(\alert{m + 1}, \bar{x}) &= h(f(\alert{m}, \bar{x}), \alert{m}, \bar{x}) \end{align*} \end{definition} \end{frame} +} + +\defineUnit{prprogramme}{% +\begin{frame} + \frametitle{PR-Programme} + \setbeamercovered{dynamic} + + U.a. diese Programme sind laut Vorlesung oder Übung PR: + \begin{itemize} + \item $pred(x) = \max \left\{ 0, x - 1 \right\}$ + \item \alert{$add(x, y) = x + y$} + \item \alert{$x \dot{-} y = \max \left\{ 0, x - y \right\}$} + \item \alert{$mult(x, y) = x \cdot y$} + \item $div(x, y) = x \div y$ (Ganzzahldivision) + \item Die restliche einfache Arithmetik\ldots + \vspace{1.5em} + \item $tower(n) = 2^{2^{2^{\iddots}}}$ mit $tower(4) = 2^{16}$ + \item $sqr(x) = x^2$, $sqrt(x) = \sqrt{x}$ + \item $c(x), p_1(x), p_2(x)$ (Cantorsche Paarungsfunktion) + \item $ifthen(n, a, b) = \begin{cases} a & n \neq 0 \\ b & n = 0 \end{cases}$ + \end{itemize} +\end{frame} +} + +\defineUnit{prerweitert}{% +\begin{frame} + \frametitle{Erweitertes PR-Schema} + \setbeamercovered{dynamic} + + \begin{definition}[Erweitertes PR-Schema] + Das \alert{erweiterte Schema der primitiven Rekursion} erlaubt + \begin{align*} + f(0, \bar{x}) &= t_0 \\ + f(m + 1, \bar{x}) &= t + \end{align*} + wobei + \begin{itemize} + \item $t_0$ enthält nur PR-Funktionen und die $x_i$ + \item $t$ enthält nur \alert{$f(m, \bar{x})$}, PR Funktionen, \alert{$m$} und die $x_i$. + \end{itemize} + \end{definition} + + \begin{theorem} + Das erweiterte Schema der primitiven Rekursion führt nicht aus \alert{PR} heraus. + \end{theorem} +\end{frame} +} + +\defineUnit{tmif}{% +\begin{frame} + \frametitle{Programmieren mit TMs} + \setbeamercovered{dynamic} + + Sind $f_1$ und $f_2$ Endzustände von $M$, so bezeichnet + \begin{center} + \begin{tikzpicture} + \node (M) at (0, 0) {$M$}; + \node[above right=0.2cm and 1cm of M] (M1) {$M_1$}; + \node[below right=0.2cm and 1cm of M] (M2) {$M_2$}; + \coordinate[right of=M1] (M1s); + \coordinate[right of=M2] (M2s); + + \draw[every edge] (-1, 0) -- (M); + \draw[every edge] (M) -- node[above left] {$f_1$} (M1); + \draw[every edge] (M) -- node[below left] {$f_2$} (M2); + \draw[every edge] (M1) -- (M1s); + \draw[every edge] (M2) -- (M2s); + \end{tikzpicture} + \end{center} + eine \alert{Fallunterscheidung}.\\ + \begin{example}[Band=0?] + \begin{align*} + \delta(q_0, 0) &= (q_0, 0, R) \\ + \delta(q_0, \square) &= (ja, \square, L) \\ + \delta(q_0, a) &= (nein, a, N) \qquad \text{für } a \neq 0, \square + \end{align*} + \end{example} +\end{frame} +} + +\defineUnit{while}{% +\begin{frame} + \frametitle{WHILE-Programme} + \setbeamercovered{dynamic} + + \begin{definition}[WHILE-Programm] + Syntax von \alert{WHILE-Programmen}.\\ + Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. + \begin{align*} + P &\rightarrow X := X + C \\ + &\mid X := X - C \\ + &\mid P; P \\ + &\mid \alert{\mathbf{WHILE}\ X \neq 0 \ \mathbf{DO}\ P \ \mathbf{END}} \\ + &\mid \textcolor{gray}{\mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END}} \\ + &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}} + \end{align*} + \end{definition} + + \begin{itemize} + \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. + \item Semantik wie erwartet. + \end{itemize} +\end{frame} +} + +\defineUnit{goto}{% +\begin{frame} + \frametitle{GOTO-Programme} + \setbeamercovered{dynamic} + + \begin{definition}[GOTO-Programm] + Syntax von \alert{GOTO-Programmen}.\\ + Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. \\ + Alle Anweisungen haben eine Markierung \alert{$M_1 : A_1; M_2 : A_2$}. + \begin{align*} + P &\rightarrow X := X + C \\ + &\mid X := X - C \\ + &\mid P; P \\ + &\mid \mathbf{GOTO}\ M_i \\ + &\mid \mathbf{IF}\ X = 0 \ \mathbf{GOTO}\ M_i \\ + &\mid \mathbf{HALT} + \end{align*} + \end{definition} + + \begin{itemize} + \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. + \end{itemize} +\end{frame} +} + +\defineUnit{loop}{% +\begin{frame} + \frametitle{LOOP-Programme} + \setbeamercovered{dynamic} + + \begin{definition}[LOOP-Programm] + Syntax von \alert{LOOP-Programmen}.\\ + Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. + \begin{align*} + P &\rightarrow X := X + C \\ + &\mid X := X - C \\ + &\mid P; P \\ + &\mid \mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END} \\ + &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}} + \end{align*} + \end{definition} + + \begin{itemize} + \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. + \item $\mathbf{LOOP}\ x_i \ \mathbf{DO}\ P \ \mathbf{END}$ führt $P$ genau $n$ mal aus, wobei $n$ der Anfangswert von $x_i$ ist. \alert{Zuweisungen an $x_i$ in $P$ ändern die Anzahl der Durchläufe nicht.} + \end{itemize} +\end{frame} +} + +\defineUnit{prmax}{% +\begin{frame} + \frametitle{Beschränkte Operationen} + \setbeamercovered{dynamic} + \begin{definition} + Ein Prädikat $P$ ist \alert{PR}, wenn es eine PR Funktion $\hat{P}$ gibt mit + \[\hat{P}(x) = 1 \Longleftrightarrow P(x)\] + \end{definition} + + \begin{definition}[Beschränkte Operationen] + Ist $P$ PR, dann auch + \begin{itemize} + \item der \alert{beschränkte max-Operator} + \[\max \left\{ x \alert{\leq n} \mid P(x) \right\}, \quad \max \left\{ \emptyset \right\} = 0\] + \item der \alert{beschränkte Existenzquantor} + \[\exists x \alert{\leq n}. P(x)\] + \end{itemize} + \end{definition} +\end{frame} +} + +\defineUnit{murekursion}{% +\begin{frame} + \frametitle{$\mu$-Rekursion} + \setbeamercovered{dynamic} + + \begin{definition}[$\mu$-Operator] + Sei $f: \N^{k+1} \to \N$ eine Funktion.\\Der \alert{$\mu$-Operator} definiert eine neue Funktion $\mu f : \N^k \to \N$: + \[(\mu f)(\bar{x}) := \begin{cases} \min \left\{ n \in \N \mid \alert{f (n, \bar{x}) = 0}\right\} & \text{falls } n \text{ existent\alert{$^*$}} \\ \perp & \text{sonst}\end{cases}\] + \end{definition} + + \vfill + + \begin{itemize} + \item \alert{$^*$}Für alle \alert{$m \leq n$} muss $f$ definiert sein: $f(m, \bar{x}) \neq \perp$ + \item PR + $\mu$ = $\mu$-Rekursion + \item In Pseudocode: + \begin{align*} + \mu f(\bar{x}) &= find(0, \bar{x}) \\ + find(n, \bar{x}) &= \mathbf{if}\ f(n, \bar{x}) = 0 \ \mathbf{then}\ n \ \mathbf{else}\ find(n+1, \bar{x}) + \end{align*} + \end{itemize} +\end{frame} +} + +\defineUnit{modelluebersetzungen}{% +\begin{frame} + \frametitle{Übersetzungen} + \setbeamercovered{dynamic} + + \begin{center} + \begin{tikzpicture}[node distance=2.5cm] + \node (WH) {WHILE}; + \node (GO) [above left of = WH] {GOTO}; + \node (TM) [above right of = WH] {TM}; + \node (LO) [below of = WH] {LOOP}; + \node (PR) [left of = LO] {PR}; + \node (MR) [left of = WH] {$\mu$R}; + + \draw [every edge, ->] (LO) -- (WH); + \draw [every edge, ->] (PR) -- (MR); + \draw [every edge, tumgreen, <->] (LO) -- (PR); + \draw [every edge, tumgreen, <->] (WH) -- (MR); + \draw [every edge, <->] (WH) -- (GO); + \draw [every edge, ->] (WH) -- (TM); + \draw [every edge, ->] (TM) -- (GO); + \end{tikzpicture} + \end{center} + + \vfill + + LOOP kann in WHILE \alert{übersetzt} werden, WHILE ist also \alert{mindestens so mächtig} wie LOOP (sogar mächtiger). +\end{frame} +} + +\defineUnit{entscheidbarkeit}{% +\begin{frame} + \frametitle{Entscheidbarkeit} + \setbeamercovered{dynamic} + + \begin{definition}[Entscheidbarkeit] + Eine Menge $A$ heißt \alert{entscheidbar} gdw ihre \alert{charakteristische Funktion} + \[ \chi_A(x) := \begin{cases}1 & \text{falls } x \in A \\ 0 & \text{falls } x \not \in A \end{cases} \] + berechenbar ist. + \end{definition} + + \begin{definition}[Semi-Entscheidbarkeit] + Eine Menge $A$ heißt \alert{semi-entscheidbar} gdw + \[ \chi'_A(x) := \begin{cases}1 & \text{falls } x \in A \\ \perp & \text{falls } x \not \in A \end{cases} \] + berechenbar ist. + \end{definition} +\end{frame} +} + +\defineUnit{breduktion}{% +\begin{frame} + \frametitle{Reduzierbarkeit} + \setbeamercovered{dynamic} + + \begin{definition}[Reduzierbarkeit] + Eine Menge $A \subseteq \Sigma^*$ ist \alert{reduzierbar} auf eine Menge $B \subseteq \Gamma^*$ gdw es eine totale und berechenbare Funktion $f:\Sigma^* \to \Gamma^*$ gibt mit + \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\] + Wir schreiben dann \alert{$A \leq B$}. + \end{definition} + + \vfill + + \structure{Intuition}: + \begin{itemize} + \item $B$ ist \alert{mindestens so schwer} zu lösen wie $A$ + \item Ist $A$ unlösbar, dann auch $B$. + \item Ist $B$ lösbar, dann erst recht $A$. + \end{itemize} +\end{frame} +} + +\defineUnit{spezielleshalteproblem}{% +\begin{frame} + \frametitle{Spezielles Halteproblem} + \setbeamercovered{dynamic} + + \begin{definition}[Spezielles Halteproblem] + Gegeben ein \structure{Wort} $w \in \left\{ 0, 1 \right\}^*$.\\ + Hält \alert{$M_w$} bei Eingabe \alert{$w$}? + \[\alert{K} := \left\{ w \mid M_w[w]\downarrow \right\}\] + \end{definition} + + \begin{theorem}[] + Das spezielle Halteproblem ist \alert{nicht entscheidbar}. + \end{theorem} + + \vfill + + \begin{itemize} + \item Hält eine Turingmaschine mit sich selbst als Eingabe? + \item $w$ ist die \structure{Gödelisierung} von $M_w$. + \item $K$ ist semi-entscheidbar, $\overline{K}$ \alert{nicht}. + \end{itemize} +\end{frame} +} + +\defineUnit{halteproblem}{% +\begin{frame} + \frametitle{Allgemeines Halteproblem} + \setbeamercovered{dynamic} + + \begin{definition}[Allgemeines Halteproblem] + Gegeben \structure{Wörter} $w, x \in \left\{ 0, 1 \right\}^*$.\\ + Hält \alert{$M_w$} bei Eingabe \alert{$x$}? + \[\alert{H} := \left\{ w\#x \mid M_w[x]\downarrow \right\}\] + \end{definition} + + \begin{theorem}[] + Das allgemeine Halteproblem ist \alert{nicht entscheidbar}. + \end{theorem} + + \vfill + + \begin{itemize} + \item Es ist $K \leq H$. Warum? + \end{itemize} +\end{frame} +} + +\defineUnit{aufzaehlbarkeit}{% +\begin{frame} + \frametitle{Rekursive Aufzählbarkeit} + \setbeamercovered{dynamic} + + \begin{definition}[Rekursiv aufzählbar] + Eine Menge $A$ heißt \alert{rekursiv aufzählbar} wenn $A = \emptyset$ oder es eine \alert{berechenbare} totale Funktion $f : \N \to A$ gibt, so dass + \[A = \left\{ f(0), f(1), \ldots \right\} = \bigcup_{n \in \N} \left\{ f(n) \right\}\] + \end{definition} + + \vfill + + \structure{Äquivalent:} + \begin{itemize} + \item $A$ rekursiv aufzählbar + \item $A$ semi-entscheidbar, also $\chi'_A$ berechenbar + \item $A=L(M)$ für eine TM $M$ + \item $A$ ist Bild oder Urbild einer berechenbaren Funktion + \end{itemize} +\end{frame} +} + +\defineUnit{rice}{% +\begin{frame} + \frametitle{Satz von Rice} + \setbeamercovered{dynamic} + + \begin{theorem}[Rice] + Sei $F$ eine Menge berechenbarer Funktionen.\\ + Sei weder $F = \emptyset$ noch $F = \text{alle ber. Funktionen}$ (\alert{$F$ nicht trivial}).\\ + Dann ist \alert{unentscheidbar}, ob die von einer gegebenen TM $M_w$ berechnete Funktion in $F$ ist, also ob \alert{$\varphi_w \in F$}. + \end{theorem} + + \begin{itemize} + \item Nicht-triviale \alert{semantische} Eigenschaften von Programmen sind unentscheidbar. + \item \alert{Termination} ist unentscheidbar. + \end{itemize} + + \vfill + + \structure{Rice-Shapiro:} + \begin{itemize} + \item Termination ist nicht semi-entscheidbar. + \item Nicht-Termination ist nicht semi-entscheidbar. + \end{itemize} +\end{frame} +} + +\defineUnit{pcp}{% +\begin{frame} + \frametitle{PCP} + \setbeamercovered{dynamic} + + \begin{definition}[Postsches Korrespondenzproblem] + Gegeben \structure{endliche Folge} $(x_1, y_1), \ldots, (x_k, y_k)$ mit $x_i, y_i \in \Sigma^+$.\\ + Gibt es eine \alert{Folge von Indizes} $i_1, \ldots, i_n \in \left\{ 1, \ldots, k \right\}$ mit \alert{\[x_{i_1}, \ldots, x_{i_n} = y_{i_1}, \ldots, y_{i_n}\]} + \end{definition} + + \vfill + + \begin{center} + \begin{tikzpicture} + \begin{scope}[start chain, node distance=2em] + \node[tape, active] {\pcp{$x_i$}{$y_i$}}; + \node[tape] (a) {\pcp{$001$}{$00$}}; + \node[tape] (b) {\pcp{$10$}{$11$}}; + \node[tape] (c) {\pcp{$1$}{$01$}}; + \end{scope} + \node[below of=a] {$1$}; + \node[below of=b] {$2$}; + \node[below of=c] {$3$}; + \end{tikzpicture} + \end{center} + + \vfill + + \begin{theorem}[] + Das PCP ist \alert{unentscheidbar}, aber semi-entscheidbar. + \end{theorem} +\end{frame} +} + +\defineUnit{pcpbeispiel}{% +\begin{frame} + \frametitle{PCP lösen} + \setbeamercovered{dynamic} + + \begin{block}{Idee} + \alert{Mögliche Lösungen} aufzählen, richtige Lösungen identifizieren + \end{block} + + \begin{center} + \begin{tikzpicture} + \begin{scope}[start chain, node distance=2em] + \node[tape, active] {\pcp{$x_i$}{$y_i$}}; + \node[tape] (a) {\pcp{$001$}{$00$}}; + \node[tape] (b) {\pcp{$01$}{$10$}}; + \node[tape] (c) {\pcp{$1$}{$11$}}; + \end{scope} + \node[below of=a] {$1$}; + \node[below of=b] {$2$}; + \node[below of=c] {$3$}; + \end{tikzpicture} + + \vspace{2em} + + \begin{tikzpicture}[grow=right, level distance = 2cm] + \tikzstyle{every node} = [] + \tikzstyle{residual} = [rectangular, thin, fill=tumgreen!10, font=\scriptsize] + \tikzstyle{edge from parent} = [every edge] + + \tikzstyle{level 1} = [sibling distance = 1.7cm] + \tikzstyle{level 2} = [sibling distance = 1.1cm] + + \node[residual] {} + child { + node[residual] {\pcp{$1$}{}} + child { + node[residual] {\pcp{$1$}{}} + child { + node[residual] {\pcp{$1$}{}} + child { + node[residual]{$\ldots$} + edge from parent + } + edge from parent + node[below] {$2$} + } + child { + node[residual, active] {\pcp{}{}} + edge from parent + node[above] {$3$} + } + edge from parent + node[below] {$2$} + } + child { + node[residual, active] {\pcp{}{}} + edge from parent + node[above] {$3$} + } + edge from parent + node[below] {$1$} + } + child { + node[residual]{\pcp{}{$1$}} + child { + node[residual]{\pcp{}{$11$}} + child { + node[residual]{$\ldots$} + edge from parent + node[above] {$3$} + } + edge from parent + node[above] {$3$} + } + edge from parent + node[above] {$3$} + }; + + \uncover<2>{\node at (10cm, 0) {$L = \left\{ (12^*3)^+ \right\}$};} + \end{tikzpicture} + \end{center} +\end{frame} +} + +\defineUnit{time}{% +\begin{frame}[t] + \frametitle{$TIME$} + \setbeamercovered{dynamic} + + \begin{definition}[$TIME$] + Wir bezeichnen die minimale Anzahl der Schritte, bis eine \structure{DTM} $M$ mit Eingabe $w$ hält als $\alert{time_M(w)} \in \N \cup \left\{ \infty \right\}$.\\ + \vspace{1em} + Sei $f : \N \to \N$ total. Dann ist + \begin{align*} + \alert{TIME(f(n))} := \{ A \subseteq \Sigma^* \mid \exists &\structure{DTM}\ M. A = L(M) \wedge \\ + &\forall w \in \Sigma^*. \structure{time_M(w) \leq f(|w|)} \} + \end{align*} + die Klasse der \structure{in Zeit $f(n)$} von einer \structure{DTM} entscheidbaren Sprachen. + \end{definition} + + \vfill + + \begin{itemize} + \item $TIME(\Oh(n))$ enthält alle "\structure{linearen Probleme}". + \item Also alle Probleme, für die ein Linearzeitalgorithmus existiert. + \end{itemize} +\end{frame} +} + +\defineUnit{ntime}{% +\begin{frame}[t] + \frametitle{$NTIME$} + \setbeamercovered{dynamic} + + \begin{definition}[$NTIME$] + Wir bezeichnen die minimale Anzahl der Schritte, bis eine \structure{NTM} $M$ mit Eingabe $w$ hält als $\alert{ntime_M(w)} \in \N$. + \[ \alert{ntime_M(w)} := \begin{cases} \text{minimale Schrittanzahl} & \text{falls } w \in L(M) \\ 0 & \text{falls } w \not \in L(M)\end{cases} \] + Dann ist + \begin{align*} + \alert{NTIME(f(n))} := \{ A \subseteq \Sigma^* \mid \exists &\structure{NTM}\ M. A = L(M) \wedge \\ + &\forall w \in \Sigma^*. \structure{ntime_M(w) \leq f(|w|)} \} + \end{align*} + die Klasse der \structure{in Zeit $f(n)$} von einer \structure{NTM} entscheidbaren Sprachen. + \end{definition} +\end{frame} +} + +\defineUnit{pundnp}{% +\begin{frame} + \frametitle{P und NP} + \setbeamercovered{dynamic} + + \begin{definition} + \alert{P} ist die Menge aller von einer \structure{DTM} in polynomieller Zeit entscheidbaren Sprachen. + \[\alert{P}:= \bigcup_{p\text{ Polynom}} TIME(p(n)) = \bigcup_{k \in \N} TIME(\alert{\Oh(n^k)}) \] + \end{definition} + + \begin{definition} + \alert{NP} ist die Menge aller von einer \structure{NTM} in polynomieller Zeit entscheidbaren Sprachen. + \[\alert{NP}:= \bigcup_{p\text{ Polynom}} NTIME(p(n)) = \bigcup_{k \in \N} NTIME(\alert{\Oh(n^k)}) \] + \end{definition} +\end{frame} +} + +\defineUnit{verifikator}{% +\begin{frame} + \frametitle{Verifikator} + \setbeamercovered{dynamic} + + \begin{definition}[Verifikator] + Sei $M$ eine \structure{DTM} mit $L(M) \subseteq \left\{ w\# c \mid w \in \Sigma^*, c \in \Delta^* \right\}$. + \begin{itemize} + \item Falls $w\#c \in L(M)$, dann heißt $c$ \alert{Zertifikat} für $w$. + \item $M$ ist ein \alert{polynomiell beschränkter Verifikator} für + \[\left\{ \structure{w \in \Sigma^*} \mid \exists c \in \Delta^* . w\#c \in L(M) \right\}\] + falls $time_M(w\#c) \leq p(|w|)$ für ein Polynom $p$. + \end{itemize} + \end{definition} + + \begin{itemize} + \item \structure{NTM} rät Lösung (Zertifikat), \structure{DTM} probiert sie aus. + \item Verifizieren (wahrscheinlich) einfacher als Lösung finden. + \end{itemize} + + \vfill + + \begin{theorem} + \alert{$A \in NP$} gdw es einen pol. beschränkten Verifikator für A gibt. + \end{theorem} +\end{frame} +} + +\defineUnit{preduktion}{% +\begin{frame} + \frametitle{Polynomielle Reduzierbarkeit} + \setbeamercovered{dynamic} + + \begin{definition}[Polynomielle Reduzierbarkeit] + Eine Menge $A \subseteq \Sigma^*$ ist \alert{polynomiell reduzierbar} auf eine Menge $B \subseteq \Gamma^*$ gdw es eine totale und \structure{von einer DTM in polynomieller Zeit} berechenbare Funktion $f:\Sigma^* \to \Gamma^*$ gibt mit + \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\] + Wir schreiben dann \alert{$A \leq_P B$}. + \end{definition} + + \vfill + + \begin{itemize} + \item Die Relation $\leq_P$ ist \structure{transitiv}. + \item P und NP sind \structure{nach unten abgeschlossen}: + \[A \leq_P B \in P/NP \Longrightarrow A \in P/NP\] + \end{itemize} +\end{frame} +} + +\defineUnit{npvollstaendigkeit}{% +\begin{frame} + \frametitle{NP-Vollständigkeit} + \setbeamercovered{dynamic} + + \begin{definition}[NP-Schwere] + Eine Sprache $L$ heißt \alert{NP-schwer} (NP-hart) wenn sich \structure{alle Sprachen} in NP auf $L$ reduzieren lassen. + \[\forall A \in NP. A \leq_P L\] + \end{definition} + + \begin{definition}[NP-Vollständigkeit] + Eine Sprache $L$ heißt \alert{NP-vollständig} wenn $L$ \structure{NP-schwer} ist und \structure{$L \in NP$}. + \end{definition} + + \vfill + + \structure{Fragen}: + \begin{itemize} + \item Gibt es überhaupt NP-vollständige Sprachen? + \item Gibt es eine NP-vollständige Sprache in $P$? + \end{itemize} +\end{frame} +} + +\defineUnit{sat}{% +\begin{frame} + \frametitle{SAT} + \setbeamercovered{dynamic} + + \begin{definition}[Aussagenlogik] + Syntax der \alert{Aussagenlogik}.\\ + \begin{description} + \item[Formeln] $F \rightarrow \neg F \mid (F \wedge F) \mid (F \vee F) \mid X$ + \item[Variablen] $X \rightarrow x \mid y \mid z \mid \ldots$ + \end{description} + \end{definition} + + \vfill + + \begin{definition}[SAT] + Gegeben eine \structure{aussagenlogische Formel} $F$.\\ + Ist $F$ \alert{erfüllbar}, also gibt es eine Belegung der Variablen in $F$, sodass $F$ gilt? + \end{definition} + + \begin{theorem}[Cook 1971] + $\mathbf{SAT}$ ist \alert{NP-vollständig}. + \end{theorem} +\end{frame} +} + +\defineUnit{3col}{% +\begin{frame} + \frametitle{3COL} + \setbeamercovered{dynamic} + + \begin{definition}[3COL] + Gegeben ein \structure{Graph} $G = (V, E)$.\\ + Gibt es eine \alert{Färbung der Knoten} $V$ mit $3$ Farben, so dass keine zwei benachbarten Knoten die gleiche Farbe haben? + \end{definition} + + \vfill + + \begin{center} + \begin{tikzpicture} + \tikzstyle{red} = [fill=tumred!50] + \tikzstyle{green} = [fill=tumgreen!50] + \tikzstyle{blue} = [fill=tumblue!50] + \tikzstyle{vertex} = [draw, circle, thin, blue] + \tikzstyle{edge} = [draw, thick] + + \foreach \name/\angle/\dist/\col in { + ia/18/0.8cm/blue, ib/90/0.8cm/red, ic/162/0.8cm/red, id/234/0.8cm/green, ie/306/0.8cm/green, + oa/18/1.6cm/red, ob/90/1.6cm/blue, oc/162/1.6cm/green, od/234/1.6cm/red, oe/306/1.6cm/blue} { + \node<1>[vertex] (\name) at (\angle:\dist) {}; + \node<2>[vertex, \col] (\name) at (\angle:\dist) {}; + } + + \foreach \a/\b in { + ia/oa, ib/ob, ic/oc, id/od, ie/oe, + oa/ob, ob/oc, oc/od, od/oe, oe/oa, + ia/ic, ic/ie, ie/ib, ib/id, id/ia} { + \draw[edge] (\a) -- (\b); + } + \end{tikzpicture} + \end{center} + + \begin{theorem} + Es ist \alert{$\mathbf{3COL} \leq_P \mathbf{SAT}$} und $\alert{\mathbf{SAT}} \leq_P \mathbf{3SAT} \alert{\leq_P \mathbf{3COL}}$. + \end{theorem} +\end{frame} +} + +\defineUnit{typ0sprachen}{% +\begin{frame} + \frametitle{Typ 0 Sprachen} + \setbeamercovered{dynamic} + + \begin{center} + \begin{tikzpicture}[node distance=2.5cm] + \node (WH) {WHILE}; + \node (GO) [above left of = WH] {GOTO}; + \node (TM) [above right of = WH] {TM}; + \node (MR) [left of = WH] {$\mu$R}; + + \draw [every edge, tumgreen, <->] (WH) -- (MR); + \draw [every edge, <->] (WH) -- (GO); + \draw [every edge, ->] (WH) -- (TM); + \draw [every edge, ->] (TM) -- (GO); + \end{tikzpicture} + \end{center} + + \vfill + + \begin{theorem}[] + Sei $A$ formale Sprache, dann ist äuqivalent: + \vspace{1em} + \begin{itemize} + \item $A$ ist \alert{Typ 0 Sprache} + \item $A$ \alert{rekursiv aufzählbar} + \item $A$ \alert{semi-entscheidbar}, also $\chi'_A$ berechenbar + \item $A=L(M)$ für eine \alert{TM $M$} + \item $A$ ist \alert{Bild oder Urbild} einer berechenbaren Funktion + \end{itemize} + \end{theorem} +\end{frame} +} + +\defineUnit{spracheigenschaften}{% +\begin{frame} + \frametitle{Spracheigenschaften} + \setbeamercovered{dynamic} + + \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\\ + TM & \structure{ja} & \structure{ja} & \structure{nein} & \structure{ja} & \structure{ja} + \end{tabu} + \end{table} + + \vfill + + \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\\ + TM & \structure{nein} & \structure{nein} & \structure{nein} & \structure{nein} + \end{tabu} + \end{table} +\end{frame} +} + +\defineUnit{formalesprachen}{% +\begin{frame}[c] + \frametitle{Formale Sprachen} + \setbeamercovered{dynamic} + + \begin{center} + \begin{tikzpicture}[auto] + \tikzstyle{rect} = [thick]; + \tikzstyle{caption} = [align=left, anchor=north west]; + + \langclass{brown}{}{0}{Formale Sprache - $\Sigma^*$}; + \langclass{tumblue}{}{1}{Typ 0 - Semi-Entscheidbar}; + \langclass{tumgreen}{}{2}{Entscheidbar}; + \langclass{violet}{}{3}{LOOP, PR}; + \langclass{tumred}{}{4}{NP}; + \langclass{tumorange}{dashed}{5}{P}; + \langclass{tumgreen!40!black}{}{6}{Typ 2 - Kontextfrei}; + \langclass{tumlightblue!80!black}{}{7}{Typ 3 - Regulär}; + \langclass{tumblue!20!black}{}{8}{Endlich}; + \end{tikzpicture} + \end{center} +\end{frame} +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/frames.tex Sun Apr 13 17:07:23 2014 +0200 @@ -0,0 +1,98 @@ +\newcommand{\defineUnit}[2]{\setbeamertemplate{slide #1}{{#2}}} +\newcommand{\showUnit}[1]{\usebeamertemplate{slide #1}} + +\defineUnit{titel}{% +\begin{frame} + \titlepage +\end{frame} +} + +\defineUnit{organisatorisches}{% +\begin{frame} + \frametitle{Organisatorisches} + + \begin{itemize} + \item Mail: \href{mailto:tutor@zfix.org}{tutor@zfix.org} + \item Web: \href{theo.zfix.org}{theo.zfix.org} + \item Hg: \href{tutor.zfix.org}{tutor.zfix.org} + \vfill + \item Wann? + \begin{itemize} + \item Dienstag 10:15-11:45 00.08.038 + \item Dienstag 12:10-13:45 00.08.038 + \end{itemize} + %\item Übungsablauf, Aufgabentypen + \item Hausaufgaben + \begin{itemize} + \item Abgabe am Montag 14h, \alert{allein} + \item Rückgabe in der \alert{richtigen} Übung + \item Notenbonus für 40\% der Punkte, 40\% in der zweiten Hälfte + \end{itemize} + \item Klausur + \begin{itemize} + \item Endterm: Mi 31.07. 11.30-14h + \item Wiederholung: Do 26.09. 11-13.30h + \end{itemize} + \end{itemize} +\end{frame} +} + +\defineUnit{wasisttheo}{% +\begin{frame} + \frametitle{Was ist Theoinf?} + + Aus der VL + \vspace{1em} + + \begin{itemize} + \item Automatentheorie + \begin{itemize} + \item Rechner mit endlichem oder kellerartigem Speicher + \end{itemize} + \vspace{0.5em} + \item Grammatiken + \begin{itemize} + \item Syntax von Programmiersprachen + \end{itemize} + \vspace{0.5em} + \item Berechenbarkeitstheorie + \begin{itemize} + \item Untersuchung der Grenzen, was Rechner prinzipiell können + \end{itemize} + \vspace{0.5em} + \item Komplexitätstheorie + \begin{itemize} + \item Untersuchung der Grenzen, was Rechner mit begrenzten Ressourcen können + \end{itemize} + \end{itemize} +\end{frame} +} + +\defineUnit{klausur}{% +\begin{frame} + \frametitle{Obacht, Klausur!} + \setbeamercovered{dynamic} + + \begin{itemize} + \item \structure{RE $\to$ $\epsilon$-NFA $\to$ NFA $\to$ DFA} + \item \structure{(Produktautomat)} + \item \structure{Quotientenautomat, Minimale DFAs} + \item Reguläres Pumpinglemma + \item \structure{CNF-Synthese} + \item \structure{Nützliche Symbole, CYK} + \item (Kellerautomaten) + \item Kontextfreies Pumpinglemma + \item Turingmaschinen + \item LOOP und PR + \item WHILE und $\mu$-Rekursion + \item Berechenbarkeit, Entscheidbarkeit, Satz von Rice + \item \structure{PCP} + \item (P und NP, Verifikatoren) + \item Reduktionen von und auf NP-Probleme + \end{itemize} +\end{frame} +} + +\input{automatons.tex} +\input{grammars.tex} +\input{computation.tex}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/grammars.tex Sun Apr 13 17:07:23 2014 +0200 @@ -0,0 +1,451 @@ +\defineUnit{grammatik}{% +\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} +} + +\defineUnit{ableitung}{% +\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} +} + +\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} ($\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} +} + +\defineUnit{cnf}{% +\begin{frame} + \frametitle{CNF} + \setbeamercovered{dynamic} + + \begin{definition}[Chomsky-Normalform] + Eine kontextfreie Grammatik ist in \alert{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}{Idee} + 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 + + \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$}; + \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$}; + \end{tikzpicture} + \end{column} + \end{columns} + \end{center} +\end{frame} +} + +\defineUnit{cyk}{% +\begin{frame} + \frametitle{CYK} + \setbeamercovered{dynamic} + + \begin{definition}[Cocke-Younger-Kasami-Algorithmus] + Der \alert{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}{Idee} + 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 \] + \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$} & \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{pda}{% +\begin{frame} + \frametitle{Kellerautomaten} + \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 endlichen Menge von \alert{Zuständen} $Q$ + \item endlichen \alert{Eingabealphabet} $\Sigma$ + \item endlichen \alert{Kelleralphabet} $\Gamma$ + \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ + \item \alert{Startzustand} $q_0 \in Q$ + \item \alert{Kellerinitialisierung} $Z_0 \in \Gamma$ + \item Menge von \alert{Endzuständen} $F \subseteq Q$ + \end{itemize} + \end{definition} + + \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 \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{definition}[Akzeptanz] + Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{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^*$ \alert{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 \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} +} + +\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} +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/preamble.tex Sun Apr 13 17:07:23 2014 +0200 @@ -0,0 +1,46 @@ +\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} +\usepackage{mathdots} +\usetikzlibrary{automata} +\usetikzlibrary{calc} +\usetikzlibrary{shapes} +\usetikzlibrary{positioning} +\usetikzlibrary{chains} +\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] + +\tikzstyle{rectangular} = [draw, rectangle, minimum size = 6mm, fill=tumblue!10] +\tikzstyle{tape} = [on chain, rectangular] +\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] + +\newcommand{\pcp}[2]{ \begin{tabu}{c} #1 \\ \tabucline{-} #2 \\ \end{tabu} } +\newcommand{\chomsky}[4]{\draw[rect, #1, fill=#1!10, #2] ({5.5 - #3 * 1}, {0 + #3 * 0.3}) rectangle ({-5.5 + #3 * 1}, {7 - #3 * 1.2}) node[caption] {#4};} +\newcommand{\langclass}[4]{\draw[rect, #1, fill=#1!20, #2] ({5.2 - #3 * 0.5}, {0 + #3 * 0.12}) rectangle ({-5.2 + #3 * 0.5}, {7.5 - #3 * 0.75}) node[caption] {#4};}