13ss.theoinf: notes/tex/automatons.tex annotate

author	Markus Kaiser <markus.kaiser@in.tum.de>
date	Thu, 11 Jul 2013 20:42:36 +0200
parents
children	35e8bb96da7b

rev	line source
41 5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	1 \defineUnit{dfa}{%
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	2 \begin{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	3 \frametitle{DFA}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	4
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	5 \begin{definition}[Deterministischer endlicher Automat]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	6 Ein \alert{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	7 \begin{itemize}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	8 \item endlichen Menge von \alert{Zuständen} $Q$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	9 \item endlichen \alert{Eingabealphabet} $\Sigma$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	10 \item totalen \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to Q$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	11 \item \alert{Startzustand} $q_0 \in Q$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	12 \item Menge von \alert{Endzuständen} $F \subseteq Q$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	13 \end{itemize}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	14 \end{definition}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	15
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	16 \vfill
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	17 \pause
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	18
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	19 \begin{center}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	20 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	21 \node[state, initial] (q0) {$q_0$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	22 \node[state, accepting] (q1) [right of = q0] {$q_1$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	23 \node[state] (q2) [right of = q1] {$q_2$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	24
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	25 \draw[->] (q0) edge [loop above] node {0} (q0);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	26 \draw[->] (q2) edge [loop above] node {1} (q2);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	27 \draw[->] (q0) edge [bend left] node {1} (q1);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	28 \draw[->] (q1) edge [bend left] node {1} (q0);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	29 \draw[->] (q1) edge [bend left] node {0} (q2);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	30 \draw[->] (q2) edge [bend left] node {0} (q1);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	31 \end{tikzpicture}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	32 \end{center}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	33 \end{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	34 }
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	35
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	36 \defineUnit{nfa}{%
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	37 \begin{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	38 \frametitle{NFA}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	39 \begin{definition}[Nicht-Deterministischer endlicher Automat]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	40 Ein \alert{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	41 \begin{itemize}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	42 \item $Q, \Sigma, q_0, F$ wie ein DFA
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	43 \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to P(Q)$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	44 \end{itemize}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	45 \end{definition}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	46
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	47 \vfill
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	48 \pause
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	49
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	50 \begin{center}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	51 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	52 \node[state, initial] (q0) {$q_0$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	53 \node[state, accepting] (q1) [right of = q0] {$q_1$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	54 \draw[->] (q0) edge [loop above] node {0,1} (q0); \draw[->] (q0) edge node {1} (q1); \end{tikzpicture} \end{center} \end{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	55 }
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	56
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	57 \defineUnit{enfa}{%
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	58 \begin{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	59 \frametitle{$\epsilon$-NFA}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	60 \begin{definition}[NFA mit $\epsilon$-Übergängen]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	61 Ein \alert{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	62 \begin{itemize}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	63 \item $Q, \Sigma, q_0, F$ wie ein DFA
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	64 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to P(Q)$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	65 \end{itemize}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	66 \end{definition}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	67
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	68 \vfill
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	69 \pause
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	70
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	71 \begin{center}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	72 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=30, initial text=]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	73 \node[state] (q1) {$q_1$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	74 \node[state, initial] (q0) [left of = q1] {$q_0$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	75 \node[state, accepting] (q2) [right of = q1] {$q_2$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	76 \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}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	77 }
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	78
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	79 \defineUnit{endlicheautomaten}{%
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	80 \begin{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	81 \frametitle{Endliche Automaten}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	82 \begin{block}{Übergangsfunktionen}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	83 Die Automaten $A = (Q, \Sigma, \delta, q_0, F)$ unterscheiden sich nur durch ihre Übergangsfunktionen.
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	84
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	85 \begin{description}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	86 \item[DFA] $\delta : Q \times \Sigma \to Q$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	87 \item[NFA] $\delta : Q \times \Sigma \to \alert{P(Q)}$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	88 \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \to \alert{P(Q)}$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	89 \end{description}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	90 \end{block}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	91
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	92 \vfill
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	93
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	94 \begin{theorem}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	95 \alert{DFA}, \alert{NFA} und \alert{$\epsilon$-NFA} sind gleich mächtig und lassen sich ineinander umwandeln.
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	96 \end{theorem}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	97 \end{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	98 }
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	99
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	100 \defineUnit{regex}{%
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	101 \begin{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	102 \frametitle{Reguläre Ausdrücke}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	103 \setbeamercovered{dynamic}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	104
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	105 \begin{definition}[Regulärer Ausdruck]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	106 \alert{Reguläre Ausdrücke} sind induktiv definiert
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	107 \begin{itemize}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	108 \item \alert{$\emptyset$} ist ein regulärer Ausdruck
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	109 \item \alert{$\epsilon$} ist ein regulärer Ausdruck
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	110 \item Für alle $a \in \Sigma$ ist \alert{$a$} ein regulärer Ausdruck
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	111 \item Sind $\alpha$ und $\beta$ reguläre Ausdrücke, dann auch
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	112 \begin{description}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	113 \item[Konkatenation] \alert{$\alpha\beta$}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	114 \item[Veroderung] \alert{$\alpha \mid \beta$}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	115 \item[Wiederholung] \alert{$\alpha^*$}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	116 \end{description}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	117 \end{itemize}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	118 Analoge Sprachdefinition, z.b. $L(\alpha\beta) = L(\alpha)L(\beta)$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	119 \end{definition}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	120
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	121 \begin{example}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	122 $\alpha = (0\|1)^*00$ \hfill $L(\alpha) = \left\{x \mid x \text{ Binärzahl}, x \mod 4 = 0 \right\}$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	123 \end{example}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	124 \end{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	125 }
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	126
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	127 \defineUnit{automatenkonversionen}{%
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	128 \begin{frame}[c]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	129 \frametitle{Konversionen}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	130 \setbeamercovered{dynamic}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	131
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	132 \begin{center}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	133 \begin{tikzpicture}[node distance=2cm]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	134 \node (nfa) {NFA};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	135 \node (dfa) [left of=nfa] {DFA};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	136 \node (enfa) [right of=nfa] {$\epsilon$-NFA};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	137 \node (re) [below of=nfa] {RE};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	138
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	139 \draw [every edge, tumred] (nfa) -- (dfa);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	140 \draw [every edge, tumred] (enfa) -- (nfa);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	141 \draw [every edge] (dfa) -- (re);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	142 \draw [every edge] (nfa) -- (re);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	143 \draw [every edge, tumred] (re) -- (enfa);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	144 \end{tikzpicture}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	145 \end{center}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	146 \end{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	147 }
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	148
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	149 \defineUnit{rezunfa}{%
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	150 \begin{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	151 \frametitle{RE $\rightarrow$ $\epsilon$-NFA}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	152 \setbeamercovered{dynamic}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	153
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	154 \begin{block}{Idee (Kleene)}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	155 Für einen Ausdruck \alert{$\gamma$} wird rekursiv mit struktureller Induktion ein $\epsilon$-NFA konstruiert.
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	156 \end{block}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	157
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	158 \begin{tabu} to \linewidth {XXX}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	159 \alert{$\gamma = \emptyset$} & \alert{$\gamma = \epsilon$} & \alert{$\gamma = a \in \Sigma$} \\
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	160 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	161 \node[state, initial] () {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	162 \end{tikzpicture} &
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	163
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	164 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	165 \node[state, initial, accepting] () {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	166 \end{tikzpicture} &
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	167
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	168 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	169 \node[state, initial] (i) {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	170 \node[state, accepting] (j) [right of=i] {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	171
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	172 \draw[->] (i) edge node {$a$} (j);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	173 \end{tikzpicture} \\
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	174 \vspace{2em}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	175 \alert{$\gamma = \alpha\beta$} \\
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	176 \multicolumn3{c}{
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	177 \begin{tikzpicture}[automaton, small]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	178 \draw[tumgreen, fill=tumgreen!20] (-0.3, 1) rectangle (1.8, -1);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	179 \node[tumgreen] () at (0.75, -1.2) {$N_\alpha$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	180
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	181 \draw[tumgreen, fill=tumgreen!20] (3.7, 1) rectangle (5.8, -1);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	182 \node[tumgreen] () at (4.75, -1.2) {$N_\beta$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	183
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	184 \node[state, initial] (i) at (0, 0) {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	185 \node[state] (j) at (1.5, 0.5) {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	186 \node[state] (k) at (1.5, -0.5) {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	187 \node[state] (l) at (4, 0) {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	188 \node[state, accepting] (m) at (5.5, 0) {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	189
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	190 \draw[->] (j) edge node {$\epsilon$} (l);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	191 \draw[->] (k) edge node {$\epsilon$} (l);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	192 \end{tikzpicture}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	193 }\\
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	194 \end{tabu}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	195 \end{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	196 }
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	197
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	198 \defineUnit{rezuenfabeispiel}{%
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	199 \begin{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	200 \frametitle{RE $\rightarrow$ $\epsilon$-NFA}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	201 \setbeamercovered{dynamic}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	202
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	203 \begin{tabu} to \linewidth {X}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	204 \alert{$\gamma = \alpha \mid \beta$} \\
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	205 \centering
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	206 \begin{tikzpicture}[automaton, small]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	207 \draw[tumgreen, fill=tumgreen!20] (2, 1.5) rectangle (4.5, 0.5);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	208 \node[tumgreen] () at (3.25, 0.3) {$N_\alpha$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	209
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	210 \draw[tumgreen, fill=tumgreen!20] (2, -0.5) rectangle (4.5, -1.5);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	211 \node[tumgreen] () at (3.25, -1.7) {$N_\beta$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	212
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	213 \node[state, initial] (i) at (0, 0) {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	214
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	215 \node[state] (j) at (2.5, 1) {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	216 \node[state, accepting] (k) at (4, 1) {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	217 \node[state] (l) at (2.5, -1) {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	218 \node[state, accepting] (m) at (4, -1) {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	219
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	220 \draw[->] (i) edge node {$\epsilon$} (j);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	221 \draw[->] (i) edge node {$\epsilon$} (l);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	222 \end{tikzpicture} \\
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	223 \vfill
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	224
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	225 \alert{$\gamma = \alpha^*$} \\
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	226 \centering
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	227 \begin{tikzpicture}[automaton, small, bend angle=70]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	228 \draw[tumgreen, fill=tumgreen!20] (2, 1) rectangle (4.5, -1);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	229 \node[tumgreen] () at (3.25, -1.2) {$N_\alpha$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	230
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	231 \node[state, initial, accepting] (i) at (0, 0) {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	232
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	233 \node[state] (j) at (2.5, 0) {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	234 \node[state, accepting] (k) at (4, 0.5) {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	235 \node[state, accepting] (m) at (4, -0.5) {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	236
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	237 \draw[->] (i) edge node {$\epsilon$} (j);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	238 \draw[->] (k) edge [bend right] node {$\epsilon$} (j);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	239 \draw[->] (m) edge [bend left] node[above] {$\epsilon$} (j);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	240 \end{tikzpicture}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	241 \end{tabu}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	242 \end{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	243 }
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	244
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	245 \defineUnit{enfazunfa}{%
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	246 \begin{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	247 \frametitle{$\epsilon$-NFA $\rightarrow$ NFA}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	248 \setbeamercovered{dynamic}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	249
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	250 \begin{block}{Idee}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	251 Entferne $\epsilon$-Kanten durch das Bilden von $\epsilon$-Hüllen.
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	252 \begin{enumerate}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	253 \item<1-> Entferne \alert{unnötige Knoten}.
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	254 \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.
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	255 \item<1,4-> Entferne alle \alert{$\epsilon$-Kanten} und unerreichbare Knoten.
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	256 \item<1,5-> Wurde das leere Wort akzeptiert mache den \alert{Anfangszustand} zum Endzustand.
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	257 \end{enumerate}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	258 \end{block}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	259
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	260 \vfill
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	261
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	262 \begin{tikzpicture}[automaton, bend angle=40, node distance=2.1cm]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	263 \useasboundingbox (-1.4,2) rectangle (9, -2);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	264
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	265 \node<-4>[state, initial] (q0) {$q_0$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	266 \node[state] (q2) [right = 3.2cm of q0] {$q_2$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	267 \node[state] (q3) [right of = q2] {$q_3$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	268 \node[state, accepting] (q4) [right of = q3] {$q_4$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	269
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	270 \draw[->] (q2) edge node {$0$} (q3);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	271 \draw[->] (q3) edge node {$1$} (q4);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	272
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	273 \draw<1-4>[->] (q3) edge [bend right] node [above] {$\epsilon$} (q2);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	274 \draw[->] (q4) edge [bend right] node [above] {$1$} (q3);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	275 \draw<1-4>[->] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	276
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	277 \node<1>[state] (q1) [right of = q0] {$q_1$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	278 \draw<1>[->] (q0) edge node {$\epsilon$} (q1);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	279 \draw<1>[->] (q1) edge node {$1$} (q2);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	280
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	281 \node<2>[state, fill=tumred!20] (q1) [right of = q0] {$q_1$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	282 \draw<2>[->, tumred] (q0) edge node {$\epsilon$} (q1);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	283 \draw<2>[->, tumred] (q1) edge node {$0$} (q2);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	284 \draw<2->[->, tumblue] (q0) edge [bend left] node {$0$} (q2);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	285
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	286 \draw<3,4,5>[->, tumred] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	287 \draw<3>[->, tumred] (q4) edge [bend right] node [above] {$1$} (q3);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	288 \draw<3,4>[->, tumred] (q3) edge [bend right] node [above] {$\epsilon$} (q2);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	289 \draw<3->[->, tumgreen] (q0) edge node {$1$} (q2);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	290
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	291 \draw<4->[->, tumgreen] (q2) edge [loop above] node [above] {$0$} (q2);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	292 \draw<4->[->, tumgreen] (q3) edge [loop above] node [above] {$0$} (q3);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	293 \draw<4->[->, tumgreen] (q0) edge [bend right=20] node [above] {$1$} (q3);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	294 \draw<4->[->, tumgreen] (q4) edge [bend right=70] node [above] {$1$} (q2);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	295
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	296 \node<5>[state, initial, accepting, fill=tumgreen!20] (q0) {$q_0$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	297
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	298 \node<6->[state, initial, accepting] (q0) {$q_0$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	299 \end{tikzpicture}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	300 \end{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	301 }
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	302
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	303 \defineUnit{nfazudfa}{%
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	304 \begin{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	305 \frametitle{NFA $\rightarrow$ DFA}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	306 \setbeamercovered{dynamic}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	307
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	308 \begin{block}{Idee (Potenzmengenkonstruktion)}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	309 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)$}.
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	310
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	311 \begin{itemize}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	312 \item $\overline{\delta}: \alert{P(Q)} \times \Sigma \to P(Q)$ \\
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	313 \[\overline{\delta}(S, a) := \bigcup_{q \in S} \delta(q, a)\]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	314 \item $F_M := \left\{S \subseteq Q \mid \alert{S \cap F} \neq \emptyset\right\}$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	315 \end{itemize}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	316 \end{block}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	317
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	318 \begin{tikzpicture}[automaton, bend angle=20, node distance=2.1cm]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	319 \useasboundingbox (-1.4,2) rectangle (9, -2);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	320
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	321 \node[state, initial] (q0) {$q_0$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	322 \node[state, accepting] (q1) [right of = q0] {$q_1$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	323
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	324 \draw[->] (q0) edge [loop above] node {$0,1$} (q0);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	325 \draw[->] (q0) edge node {$1$} (q1);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	326
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	327 \node<2->(sep) [right of = q1] {$\rightarrow$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	328
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	329 \node<2->[state, initial, inner sep=1pt] (pq0) [right of = sep] {$q_{\{0\}}$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	330
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	331 \node<3->[state, accepting, inner sep=0pt] (pq01) [right of = pq0] {$q_{\{0,1\}}$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	332 \draw<3->[->] (pq0) edge [loop above] node {$0$} (pq0);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	333 \draw<3->[->] (pq0) edge [bend left] node {$1$} (pq01);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	334
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	335 \draw<4->[->] (pq01) edge [loop above] node {$1$} (pq01);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	336 \draw<4->[->] (pq01) edge [bend left] node {$0$} (pq0);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	337
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	338 \end{tikzpicture}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	339 \end{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	340 }
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	341
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	342 \defineUnit{produktautomat}{%
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	343 \begin{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	344 \frametitle{produktautomat}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	345 \setbeamercovered{dynamic}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	346 \begin{theorem}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	347 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}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	348
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	349 \begin{align*}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	350 m &:= (\alert{q_1 \times q_2}, \sigma, \delta, (s_1, s_2), f_1 \times f_2) \\
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	351 \delta\left( (q_1, q_2), a \right) &:= \left( \alert{\delta_1}(q_1, a), \alert{\delta_2}(q_2, a) \right)
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	352 \end{align*}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	353
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	354 ein dfa, der $l(m_1) \cap l(m_2)$ akzeptiert.
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	355 \end{theorem}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	356 \end{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	357 }
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	358
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	359 \defineUnit{regexrechnen}{%
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	360 \begin{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	361 \frametitle{Nochmal Reguläre Ausdrücke}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	362 \setbeamercovered{dynamic}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	363
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	364 \begin{theorem}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	365 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$.
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	366
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	367 \begin{itemize}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	368 \item \alert{Assoziative} Operationen
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	369 \item Veroderung \alert{kommutativ}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	370 \item \alert{Distributivität}: $\alpha (\beta \mid \gamma) \equiv \alpha\beta \mid \alpha\gamma$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	371 \item $\emptyset$ \alert{neutral} bezüglich Oder
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	372 \item $\epsilon$ \alert{neutral} bezüglich Konkatenation
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	373 \end{itemize}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	374 \end{theorem}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	375
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	376 \begin{example}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	377 \[
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	378 1\psi \mid 0\phi \mid \psi \equiv 0 \phi \mid (1 \mid \epsilon) \psi
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	379 \]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	380 \end{example}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	381 \end{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	382 }
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	383
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	384 \defineUnit{arden}{%
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	385 \begin{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	386 \frametitle{Ardens Lemma}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	387 \setbeamercovered{dynamic}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	388
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	389 \begin{theorem}[Ardens Lemma]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	390 Sind $A$, $B$ und $X$ Sprachen mit $\epsilon \not \in A$, dann gilt
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	391 \[
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	392 X = AX \cup B \Longrightarrow X = A^* B
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	393 \]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	394 Speziell gilt für reguläre Ausdrücke
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	395 \[
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	396 X \equiv \alpha X \mid \beta \Longrightarrow X \equiv \alpha^* \beta
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	397 \]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	398 \end{theorem}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	399
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	400 \begin{example}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	401 \[
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	402 \psi \equiv 0 \psi \mid (1 \mid \epsilon) \phi \Longrightarrow \psi \equiv 0^*(1\mid \epsilon) \phi
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	403 \]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	404 \end{example}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	405 \end{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	406 }
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	407
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	408 \defineUnit{nfazure}{%
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	409 \begin{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	410 \frametitle{NFA $\rightarrow$ RE}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	411 \setbeamercovered{dynamic}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	412
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	413 \begin{block}{Idee}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	414 Erzeuge ein Gleichungssystem aus allen Zuständen.
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	415 \begin{enumerate}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	416 \item<1,2-> Ausdruck für jeden Zustand
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	417 \item<1,3-> Auflösen nach $X_0$ mit Algebra und Ardens Lemma
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	418 \end{enumerate}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	419 \end{block}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	420 \begin{columns}<2->
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	421 \begin{column}[b]{.65\textwidth}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	422 \begin{align*}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	423 X_0 &\equiv 1X_0 \mid 0X_1 \\
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	424 &\equiv \uncover<4->{1X_0 \mid 00^*(\epsilon \mid 1X_0)} \\
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	425 &\equiv \uncover<4->{(1 \mid 00^1) X_0 \mid 00^} \\
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	426 &\equiv \uncover<4->{(1 \mid 00^1)^(00^*)} \\
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	427 \\
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	428 X_1 &\equiv 1X_0 \mid 0X_1 \alt<3->{\mid \epsilon}{\alert{\mid \epsilon}} \\
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	429 &\equiv \uncover<3-> {0X_1 \mid (\epsilon \mid 1 X_0)}\\
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	430 &\equiv \uncover<3-> {\alt<-2,4->{0^(\epsilon \mid 1X_0)}{\alert{0^(\epsilon \mid 1X_0)}}}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	431 \end{align*}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	432 \end{column}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	433 \begin{column}[t]{.35\textwidth}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	434 \begin{tikzpicture}[automaton]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	435 \node[state, initial] (q0) {$q_0$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	436 \node[state, accepting] (q1) [below of=q0] {$q_1$};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	437
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	438 \draw[->] (q0) edge [bend right] node [left] {$0$} (q1);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	439 \draw[->] (q1) edge [bend right] node [right] {$1$} (q0);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	440 \draw[->] (q0) edge [loop right] node {$1$} (q0);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	441 \draw[->] (q1) edge [loop right] node {$0$} (q1);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	442 \end{tikzpicture}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	443 \end{column}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	444 \end{columns}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	445 \end{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	446 }
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	447
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	448 \defineUnit{rpl}{%
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	449 \begin{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	450 \frametitle{Pumping Lemma}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	451 \setbeamercovered{dynamic}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	452
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	453 \begin{theorem}[Pumping Lemma für reguläre Sprachen]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	454 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
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	455 \begin{itemize}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	456 \item $v \neq \epsilon$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	457 \item $\|uv\| \alert{\leq n}$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	458 \item $\forall i \alert{\geq 0}. uv^iw \in R$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	459 \end{itemize}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	460 \end{theorem}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	461
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	462 \vfill
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	463
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	464 \begin{center}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	465 \begin{tikzpicture}[automaton]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	466 \node[state, initial] (q0) {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	467 \node[state, fill=tumred!20] (q1) [right of=q0] {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	468 \node[state, accepting] (q2) [right of=q1] {};
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	469
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	470 \draw[->, densely dashed] (q0) edge node {$u$} (q1);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	471 \draw[->, tumred] (q1) edge [loop above] node {$v$} (q1);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	472 \draw[->, densely dashed] (q1) edge node {$w$} (q2);
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	473 \end{tikzpicture}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	474 \end{center}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	475 \end{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	476 }
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	477
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	478 \defineUnit{rplanwenden}{%
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	479 \begin{frame}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	480 \frametitle{Nichtregularität beweisen}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	481 \setbeamercovered{dynamic}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	482
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	483 \begin{block}{Idee}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	484 Gegenbeispiel fürs Pumpinglemma suchen.
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	485 \[
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	486 \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}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	487 \]
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	488 \end{block}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	489
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	490 \vfill
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	491
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	492 \begin{example}<2->
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	493 Ist $L = \left\{ a^ib^i \mid i \in \N_0 \right\}$ regulär?
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	494 \begin{enumerate}
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	495 \item \alert{Sei $n$} PL-Zahl
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	496 \item \alert{Wähle} $\alert{z} = a^nb^n$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	497 \item Dann ist \alert{$z = uvw$} mit \alert{$\|uv\| \leq n$}, hier: $v=a^k$ mit $k > 0$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	498 \item Dann ist $uv^0w \not \in L$
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	499 \item Damit ist L \alert{nicht} regulär.
5d10471f5585 move frame-definitions out of presentations Markus Kaiser <markus.kaiser@in.tum.de> parents: diff changeset	500 \end{enumerate}

41

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

1 \defineUnit{dfa}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

2 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

3 \frametitle{DFA}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

4

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

5 \begin{definition}[Deterministischer endlicher Automat]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

6 Ein \alert{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

7 \begin{itemize}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

8 \item endlichen Menge von \alert{Zuständen} $Q$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

9 \item endlichen \alert{Eingabealphabet} $\Sigma$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

10 \item totalen \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to Q$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

11 \item \alert{Startzustand} $q_0 \in Q$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

12 \item Menge von \alert{Endzuständen} $F \subseteq Q$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

13 \end{itemize}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

14 \end{definition}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

15

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

16 \vfill

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

17 \pause

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

18

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

19 \begin{center}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

20 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

21 \node[state, initial] (q0) {$q_0$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

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

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

23 \node[state] (q2) [right of = q1] {$q_2$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

24

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

25 \draw[->] (q0) edge [loop above] node {0} (q0);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

26 \draw[->] (q2) edge [loop above] node {1} (q2);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

27 \draw[->] (q0) edge [bend left] node {1} (q1);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

28 \draw[->] (q1) edge [bend left] node {1} (q0);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

29 \draw[->] (q1) edge [bend left] node {0} (q2);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

30 \draw[->] (q2) edge [bend left] node {0} (q1);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

31 \end{tikzpicture}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

32 \end{center}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

33 \end{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

34 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

35

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

36 \defineUnit{nfa}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

37 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

38 \frametitle{NFA}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

39 \begin{definition}[Nicht-Deterministischer endlicher Automat]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

40 Ein \alert{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

41 \begin{itemize}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

42 \item $Q, \Sigma, q_0, F$ wie ein DFA

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

43 \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to P(Q)$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

44 \end{itemize}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

45 \end{definition}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

46

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

47 \vfill

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

48 \pause

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

49

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

50 \begin{center}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

51 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

52 \node[state, initial] (q0) {$q_0$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

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

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

54 \draw[->] (q0) edge [loop above] node {0,1} (q0); \draw[->] (q0) edge node {1} (q1); \end{tikzpicture} \end{center} \end{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

55 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

56

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

57 \defineUnit{enfa}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

58 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

59 \frametitle{$\epsilon$-NFA}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

60 \begin{definition}[NFA mit $\epsilon$-Übergängen]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

61 Ein \alert{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

62 \begin{itemize}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

63 \item $Q, \Sigma, q_0, F$ wie ein DFA

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

64 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to P(Q)$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

65 \end{itemize}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

66 \end{definition}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

67

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

68 \vfill

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

69 \pause

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

70

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

71 \begin{center}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

72 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=30, initial text=]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

73 \node[state] (q1) {$q_1$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

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

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

75 \node[state, accepting] (q2) [right of = q1] {$q_2$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

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

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

77 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

78

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

79 \defineUnit{endlicheautomaten}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

80 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

81 \frametitle{Endliche Automaten}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

82 \begin{block}{Übergangsfunktionen}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

83 Die Automaten $A = (Q, \Sigma, \delta, q_0, F)$ unterscheiden sich nur durch ihre Übergangsfunktionen.

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

84

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

85 \begin{description}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

86 \item[DFA] $\delta : Q \times \Sigma \to Q$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

87 \item[NFA] $\delta : Q \times \Sigma \to \alert{P(Q)}$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

88 \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \to \alert{P(Q)}$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

89 \end{description}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

90 \end{block}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

91

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

92 \vfill

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

93

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

94 \begin{theorem}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

95 \alert{DFA}, \alert{NFA} und \alert{$\epsilon$-NFA} sind gleich mächtig und lassen sich ineinander umwandeln.

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

96 \end{theorem}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

97 \end{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

98 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

99

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

100 \defineUnit{regex}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

101 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

102 \frametitle{Reguläre Ausdrücke}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

103 \setbeamercovered{dynamic}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

104

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

105 \begin{definition}[Regulärer Ausdruck]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

106 \alert{Reguläre Ausdrücke} sind induktiv definiert

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

107 \begin{itemize}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

108 \item \alert{$\emptyset$} ist ein regulärer Ausdruck

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

109 \item \alert{$\epsilon$} ist ein regulärer Ausdruck

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

110 \item Für alle $a \in \Sigma$ ist \alert{$a$} ein regulärer Ausdruck

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

111 \item Sind $\alpha$ und $\beta$ reguläre Ausdrücke, dann auch

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

112 \begin{description}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

113 \item[Konkatenation] \alert{$\alpha\beta$}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

114 \item[Veroderung] \alert{$\alpha \mid \beta$}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

115 \item[Wiederholung] \alert{$\alpha^*$}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

116 \end{description}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

117 \end{itemize}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

118 Analoge Sprachdefinition, z.b. $L(\alpha\beta) = L(\alpha)L(\beta)$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

119 \end{definition}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

120

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

121 \begin{example}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

122 $\alpha = (0|1)^*00$ \hfill $L(\alpha) = \left\{x \mid x \text{ Binärzahl}, x \mod 4 = 0 \right\}$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

123 \end{example}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

124 \end{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

125 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

126

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

127 \defineUnit{automatenkonversionen}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

128 \begin{frame}[c]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

129 \frametitle{Konversionen}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

130 \setbeamercovered{dynamic}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

131

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

132 \begin{center}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

133 \begin{tikzpicture}[node distance=2cm]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

134 \node (nfa) {NFA};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

135 \node (dfa) [left of=nfa] {DFA};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

136 \node (enfa) [right of=nfa] {$\epsilon$-NFA};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

137 \node (re) [below of=nfa] {RE};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

138

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

139 \draw [every edge, tumred] (nfa) -- (dfa);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

140 \draw [every edge, tumred] (enfa) -- (nfa);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

141 \draw [every edge] (dfa) -- (re);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

142 \draw [every edge] (nfa) -- (re);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

143 \draw [every edge, tumred] (re) -- (enfa);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

144 \end{tikzpicture}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

145 \end{center}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

146 \end{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

147 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

148

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

149 \defineUnit{rezunfa}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

150 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

151 \frametitle{RE $\rightarrow$ $\epsilon$-NFA}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

152 \setbeamercovered{dynamic}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

153

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

154 \begin{block}{Idee (Kleene)}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

155 Für einen Ausdruck \alert{$\gamma$} wird rekursiv mit struktureller Induktion ein $\epsilon$-NFA konstruiert.

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

156 \end{block}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

157

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

158 \begin{tabu} to \linewidth {XXX}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

159 \alert{$\gamma = \emptyset$} & \alert{$\gamma = \epsilon$} & \alert{$\gamma = a \in \Sigma$} \\

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

160 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

161 \node[state, initial] () {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

162 \end{tikzpicture} &

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

163

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

164 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

165 \node[state, initial, accepting] () {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

166 \end{tikzpicture} &

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

167

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

168 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

169 \node[state, initial] (i) {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

170 \node[state, accepting] (j) [right of=i] {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

171

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

172 \draw[->] (i) edge node {$a$} (j);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

173 \end{tikzpicture} \\

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

174 \vspace{2em}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

175 \alert{$\gamma = \alpha\beta$} \\

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

176 \multicolumn3{c}{

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

177 \begin{tikzpicture}[automaton, small]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

178 \draw[tumgreen, fill=tumgreen!20] (-0.3, 1) rectangle (1.8, -1);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

179 \node[tumgreen] () at (0.75, -1.2) {$N_\alpha$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

180

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

181 \draw[tumgreen, fill=tumgreen!20] (3.7, 1) rectangle (5.8, -1);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

182 \node[tumgreen] () at (4.75, -1.2) {$N_\beta$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

183

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

184 \node[state, initial] (i) at (0, 0) {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

185 \node[state] (j) at (1.5, 0.5) {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

186 \node[state] (k) at (1.5, -0.5) {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

187 \node[state] (l) at (4, 0) {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

188 \node[state, accepting] (m) at (5.5, 0) {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

189

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

190 \draw[->] (j) edge node {$\epsilon$} (l);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

191 \draw[->] (k) edge node {$\epsilon$} (l);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

192 \end{tikzpicture}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

193 }\\

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

194 \end{tabu}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

195 \end{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

196 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

197

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

198 \defineUnit{rezuenfabeispiel}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

199 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

200 \frametitle{RE $\rightarrow$ $\epsilon$-NFA}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

201 \setbeamercovered{dynamic}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

202

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

203 \begin{tabu} to \linewidth {X}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

204 \alert{$\gamma = \alpha \mid \beta$} \\

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

205 \centering

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

206 \begin{tikzpicture}[automaton, small]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

207 \draw[tumgreen, fill=tumgreen!20] (2, 1.5) rectangle (4.5, 0.5);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

208 \node[tumgreen] () at (3.25, 0.3) {$N_\alpha$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

209

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

210 \draw[tumgreen, fill=tumgreen!20] (2, -0.5) rectangle (4.5, -1.5);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

211 \node[tumgreen] () at (3.25, -1.7) {$N_\beta$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

212

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

213 \node[state, initial] (i) at (0, 0) {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

214

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

215 \node[state] (j) at (2.5, 1) {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

216 \node[state, accepting] (k) at (4, 1) {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

217 \node[state] (l) at (2.5, -1) {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

218 \node[state, accepting] (m) at (4, -1) {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

219

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

220 \draw[->] (i) edge node {$\epsilon$} (j);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

221 \draw[->] (i) edge node {$\epsilon$} (l);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

222 \end{tikzpicture} \\

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

223 \vfill

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

224

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

225 \alert{$\gamma = \alpha^*$} \\

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

226 \centering

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

227 \begin{tikzpicture}[automaton, small, bend angle=70]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

228 \draw[tumgreen, fill=tumgreen!20] (2, 1) rectangle (4.5, -1);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

229 \node[tumgreen] () at (3.25, -1.2) {$N_\alpha$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

230

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

231 \node[state, initial, accepting] (i) at (0, 0) {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

232

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

233 \node[state] (j) at (2.5, 0) {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

234 \node[state, accepting] (k) at (4, 0.5) {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

235 \node[state, accepting] (m) at (4, -0.5) {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

236

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

237 \draw[->] (i) edge node {$\epsilon$} (j);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

238 \draw[->] (k) edge [bend right] node {$\epsilon$} (j);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

239 \draw[->] (m) edge [bend left] node[above] {$\epsilon$} (j);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

240 \end{tikzpicture}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

241 \end{tabu}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

242 \end{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

243 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

244

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

245 \defineUnit{enfazunfa}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

246 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

247 \frametitle{$\epsilon$-NFA $\rightarrow$ NFA}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

248 \setbeamercovered{dynamic}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

249

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

250 \begin{block}{Idee}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

251 Entferne $\epsilon$-Kanten durch das Bilden von $\epsilon$-Hüllen.

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

252 \begin{enumerate}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

253 \item<1-> Entferne \alert{unnötige Knoten}.

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

254 \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.

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

255 \item<1,4-> Entferne alle \alert{$\epsilon$-Kanten} und unerreichbare Knoten.

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

256 \item<1,5-> Wurde das leere Wort akzeptiert mache den \alert{Anfangszustand} zum Endzustand.

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

257 \end{enumerate}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

258 \end{block}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

259

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

260 \vfill

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

261

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

262 \begin{tikzpicture}[automaton, bend angle=40, node distance=2.1cm]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

263 \useasboundingbox (-1.4,2) rectangle (9, -2);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

264

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

265 \node<-4>[state, initial] (q0) {$q_0$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

266 \node[state] (q2) [right = 3.2cm of q0] {$q_2$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

267 \node[state] (q3) [right of = q2] {$q_3$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

268 \node[state, accepting] (q4) [right of = q3] {$q_4$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

269

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

270 \draw[->] (q2) edge node {$0$} (q3);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

271 \draw[->] (q3) edge node {$1$} (q4);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

272

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

273 \draw<1-4>[->] (q3) edge [bend right] node [above] {$\epsilon$} (q2);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

274 \draw[->] (q4) edge [bend right] node [above] {$1$} (q3);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

275 \draw<1-4>[->] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

276

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

277 \node<1>[state] (q1) [right of = q0] {$q_1$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

278 \draw<1>[->] (q0) edge node {$\epsilon$} (q1);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

279 \draw<1>[->] (q1) edge node {$1$} (q2);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

280

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

281 \node<2>[state, fill=tumred!20] (q1) [right of = q0] {$q_1$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

282 \draw<2>[->, tumred] (q0) edge node {$\epsilon$} (q1);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

283 \draw<2>[->, tumred] (q1) edge node {$0$} (q2);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

284 \draw<2->[->, tumblue] (q0) edge [bend left] node {$0$} (q2);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

285

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

286 \draw<3,4,5>[->, tumred] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

287 \draw<3>[->, tumred] (q4) edge [bend right] node [above] {$1$} (q3);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

288 \draw<3,4>[->, tumred] (q3) edge [bend right] node [above] {$\epsilon$} (q2);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

289 \draw<3->[->, tumgreen] (q0) edge node {$1$} (q2);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

290

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

291 \draw<4->[->, tumgreen] (q2) edge [loop above] node [above] {$0$} (q2);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

292 \draw<4->[->, tumgreen] (q3) edge [loop above] node [above] {$0$} (q3);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

293 \draw<4->[->, tumgreen] (q0) edge [bend right=20] node [above] {$1$} (q3);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

294 \draw<4->[->, tumgreen] (q4) edge [bend right=70] node [above] {$1$} (q2);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

295

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

296 \node<5>[state, initial, accepting, fill=tumgreen!20] (q0) {$q_0$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

297

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

298 \node<6->[state, initial, accepting] (q0) {$q_0$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

299 \end{tikzpicture}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

300 \end{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

301 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

302

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

303 \defineUnit{nfazudfa}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

304 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

305 \frametitle{NFA $\rightarrow$ DFA}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

306 \setbeamercovered{dynamic}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

307

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

308 \begin{block}{Idee (Potenzmengenkonstruktion)}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

309 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)$}.

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

310

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

311 \begin{itemize}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

312 \item $\overline{\delta}: \alert{P(Q)} \times \Sigma \to P(Q)$ \\

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

313 \[\overline{\delta}(S, a) := \bigcup_{q \in S} \delta(q, a)\]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

314 \item $F_M := \left\{S \subseteq Q \mid \alert{S \cap F} \neq \emptyset\right\}$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

315 \end{itemize}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

316 \end{block}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

317

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

318 \begin{tikzpicture}[automaton, bend angle=20, node distance=2.1cm]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

319 \useasboundingbox (-1.4,2) rectangle (9, -2);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

320

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

321 \node[state, initial] (q0) {$q_0$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

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

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

323

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

324 \draw[->] (q0) edge [loop above] node {$0,1$} (q0);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

325 \draw[->] (q0) edge node {$1$} (q1);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

326

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

327 \node<2->(sep) [right of = q1] {$\rightarrow$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

328

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

329 \node<2->[state, initial, inner sep=1pt] (pq0) [right of = sep] {$q_{\{0\}}$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

330

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

331 \node<3->[state, accepting, inner sep=0pt] (pq01) [right of = pq0] {$q_{\{0,1\}}$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

332 \draw<3->[->] (pq0) edge [loop above] node {$0$} (pq0);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

333 \draw<3->[->] (pq0) edge [bend left] node {$1$} (pq01);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

334

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

335 \draw<4->[->] (pq01) edge [loop above] node {$1$} (pq01);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

336 \draw<4->[->] (pq01) edge [bend left] node {$0$} (pq0);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

337

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

338 \end{tikzpicture}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

339 \end{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

340 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

341

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

342 \defineUnit{produktautomat}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

343 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

344 \frametitle{produktautomat}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

345 \setbeamercovered{dynamic}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

346 \begin{theorem}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

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

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

348

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

349 \begin{align*}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

350 m &:= (\alert{q_1 \times q_2}, \sigma, \delta, (s_1, s_2), f_1 \times f_2) \\

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

351 \delta\left( (q_1, q_2), a \right) &:= \left( \alert{\delta_1}(q_1, a), \alert{\delta_2}(q_2, a) \right)

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

352 \end{align*}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

353

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

354 ein dfa, der $l(m_1) \cap l(m_2)$ akzeptiert.

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

355 \end{theorem}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

356 \end{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

357 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

358

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

359 \defineUnit{regexrechnen}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

360 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

361 \frametitle{Nochmal Reguläre Ausdrücke}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

362 \setbeamercovered{dynamic}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

363

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

364 \begin{theorem}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

365 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$.

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

366

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

367 \begin{itemize}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

368 \item \alert{Assoziative} Operationen

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

369 \item Veroderung \alert{kommutativ}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

370 \item \alert{Distributivität}: $\alpha (\beta \mid \gamma) \equiv \alpha\beta \mid \alpha\gamma$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

371 \item $\emptyset$ \alert{neutral} bezüglich Oder

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

372 \item $\epsilon$ \alert{neutral} bezüglich Konkatenation

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

373 \end{itemize}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

374 \end{theorem}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

375

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

376 \begin{example}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

377 \[

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

378 1\psi \mid 0\phi \mid \psi \equiv 0 \phi \mid (1 \mid \epsilon) \psi

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

379 \]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

380 \end{example}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

381 \end{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

382 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

383

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

384 \defineUnit{arden}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

385 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

386 \frametitle{Ardens Lemma}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

387 \setbeamercovered{dynamic}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

388

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

389 \begin{theorem}[Ardens Lemma]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

390 Sind $A$, $B$ und $X$ Sprachen mit $\epsilon \not \in A$, dann gilt

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

391 \[

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

392 X = AX \cup B \Longrightarrow X = A^* B

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

393 \]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

394 Speziell gilt für reguläre Ausdrücke

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

395 \[

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

396 X \equiv \alpha X \mid \beta \Longrightarrow X \equiv \alpha^* \beta

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

397 \]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

398 \end{theorem}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

399

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

400 \begin{example}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

401 \[

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

402 \psi \equiv 0 \psi \mid (1 \mid \epsilon) \phi \Longrightarrow \psi \equiv 0^*(1\mid \epsilon) \phi

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

403 \]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

404 \end{example}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

405 \end{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

406 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

407

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

408 \defineUnit{nfazure}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

409 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

410 \frametitle{NFA $\rightarrow$ RE}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

411 \setbeamercovered{dynamic}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

412

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

413 \begin{block}{Idee}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

414 Erzeuge ein Gleichungssystem aus allen Zuständen.

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

415 \begin{enumerate}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

416 \item<1,2-> Ausdruck für jeden Zustand

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

417 \item<1,3-> Auflösen nach $X_0$ mit Algebra und Ardens Lemma

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

418 \end{enumerate}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

419 \end{block}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

420 \begin{columns}<2->

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

421 \begin{column}[b]{.65\textwidth}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

422 \begin{align*}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

423 X_0 &\equiv 1X_0 \mid 0X_1 \\

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

424 &\equiv \uncover<4->{1X_0 \mid 00^*(\epsilon \mid 1X_0)} \\

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

425 &\equiv \uncover<4->{(1 \mid 00^*1) X_0 \mid 00^*} \\

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

426 &\equiv \uncover<4->{(1 \mid 00^*1)^*(00^*)} \\

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

427 \\

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

428 X_1 &\equiv 1X_0 \mid 0X_1 \alt<3->{\mid \epsilon}{\alert{\mid \epsilon}} \\

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

429 &\equiv \uncover<3-> {0X_1 \mid (\epsilon \mid 1 X_0)}\\

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

430 &\equiv \uncover<3-> {\alt<-2,4->{0^*(\epsilon \mid 1X_0)}{\alert{0^*(\epsilon \mid 1X_0)}}}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

431 \end{align*}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

432 \end{column}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

433 \begin{column}[t]{.35\textwidth}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

434 \begin{tikzpicture}[automaton]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

435 \node[state, initial] (q0) {$q_0$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

436 \node[state, accepting] (q1) [below of=q0] {$q_1$};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

437

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

438 \draw[->] (q0) edge [bend right] node [left] {$0$} (q1);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

439 \draw[->] (q1) edge [bend right] node [right] {$1$} (q0);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

440 \draw[->] (q0) edge [loop right] node {$1$} (q0);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

441 \draw[->] (q1) edge [loop right] node {$0$} (q1);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

442 \end{tikzpicture}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

443 \end{column}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

444 \end{columns}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

445 \end{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

446 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

447

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

448 \defineUnit{rpl}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

449 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

450 \frametitle{Pumping Lemma}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

451 \setbeamercovered{dynamic}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

452

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

453 \begin{theorem}[Pumping Lemma für reguläre Sprachen]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

454 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

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

455 \begin{itemize}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

456 \item $v \neq \epsilon$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

457 \item $|uv| \alert{\leq n}$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

458 \item $\forall i \alert{\geq 0}. uv^iw \in R$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

459 \end{itemize}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

460 \end{theorem}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

461

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

462 \vfill

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

463

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

464 \begin{center}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

465 \begin{tikzpicture}[automaton]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

466 \node[state, initial] (q0) {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

467 \node[state, fill=tumred!20] (q1) [right of=q0] {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

468 \node[state, accepting] (q2) [right of=q1] {};

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

469

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

470 \draw[->, densely dashed] (q0) edge node {$u$} (q1);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

471 \draw[->, tumred] (q1) edge [loop above] node {$v$} (q1);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

472 \draw[->, densely dashed] (q1) edge node {$w$} (q2);

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

473 \end{tikzpicture}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

474 \end{center}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

475 \end{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

476 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

477

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

478 \defineUnit{rplanwenden}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

479 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

480 \frametitle{Nichtregularität beweisen}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

481 \setbeamercovered{dynamic}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

482

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

483 \begin{block}{Idee}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

484 Gegenbeispiel fürs Pumpinglemma suchen.

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

485 \[

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

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

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

487 \]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

488 \end{block}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

489

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

490 \vfill

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

491

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

492 \begin{example}<2->

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

493 Ist $L = \left\{ a^ib^i \mid i \in \N_0 \right\}$ regulär?

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

494 \begin{enumerate}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

495 \item \alert{Sei $n$} PL-Zahl

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

496 \item \alert{Wähle} $\alert{z} = a^nb^n$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

497 \item Dann ist \alert{$z = uvw$} mit \alert{$|uv| \leq n$}, hier: $v=a^k$ mit $k > 0$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

498 \item Dann ist $uv^0w \not \in L$

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

499 \item Damit ist L \alert{nicht} regulär.

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

500 \end{enumerate}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

501 \end{example}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

502 \end{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

503 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

504

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

505 \defineUnit{aequivalenteZustaende}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

506 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

507 \frametitle{Äquivalenzen}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

508 \setbeamercovered{dynamic}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

509

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

510 \begin{definition}[Äquivalente Worte]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

511 Jede Sprache $L \subseteq \Sigma^*$ induziert eine Äquivalenzrelation $\alert{\equiv_L \subseteq \Sigma^* \times \Sigma^*}$:

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

512 \[

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

513 u \alert{\equiv_L} v \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{uw} \in L \Leftrightarrow \alert{vw} \in L\right)

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

514 \]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

515 \end{definition}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

516

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

517 \vfill

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

518

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

519 \pause

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

520

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

521 \begin{definition}[Äquivalente Zustände]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

522 Zwei Zustände im DFA $A$ sind \alert{äquivalent} wenn sie die selbe Sprache akzeptieren.

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

523

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

524 \[

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

525 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)

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

526 \]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

527 \end{definition}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

528 \end{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

529 }

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

530

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

531 \defineUnit{unterscheidbareZustaende}{%

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

532 \begin{frame}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

533 \frametitle{Unterscheidbare Zustände}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

534 \setbeamercovered{dynamic}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

535

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

536 \begin{definition}[Unterscheidbarkeit]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

537 Zwei Zustände sind \alert{unterscheidbar}, wenn sie unterschiedliche Sprachen akzeptieren.

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

538 \[

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

539 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)

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

540 \]

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>

parents:

diff changeset

541 \end{definition}

5d10471f5585 move frame-definitions out of presentations

Markus Kaiser <markus.kaiser@in.tum.de>