14ss.theoinf: notes/tex/automatons.tex comparison

comparison notes/tex/automatons.tex @ 13:834da46b1edb

third sheet and notes

author	Markus Kaiser <markus.kaiser@in.tum.de>
date	Sat, 03 May 2014 22:49:43 +0200
parents	11723d02ee58
children	d5b561a49683

comparison

equal deleted inserted replaced

-:11723d02ee58
+:834da46b1edb
 \begin{frame}
 \frametitle{Reguläre Ausdrücke}
 \setbeamercovered{dynamic}
 \begin{definition}[Regulärer Ausdruck]
-\alert{Reguläre Ausdrücke} sind induktiv definiert
+\structure{Reguläre Ausdrücke} sind induktiv definiert
 \begin{itemize}
-\item \alert{$\emptyset$} ist ein regulärer Ausdruck
+\item \structure{$\emptyset$} ist ein regulärer Ausdruck
-\item \alert{$\epsilon$} ist ein regulärer Ausdruck
+\item \structure{$\epsilon$} ist ein regulärer Ausdruck
-\item Für alle $a \in \Sigma$ ist \alert{$a$} ein regulärer Ausdruck
+\item Für alle $a \in \Sigma$ ist \structure{$a$} ein regulärer Ausdruck
 \item Sind $\alpha$ und $\beta$ reguläre Ausdrücke, dann auch
-\begin{description}
+\begin{description}[Konkatenation]
-\item[Konkatenation] \alert{$\alpha\beta$}
+\item[Konkatenation] \structure{$\alpha\beta$}
-\item[Veroderung] \alert{$\alpha \mid \beta$}
+\item[Veroderung] \structure{$\alpha \mid \beta$}
-\item[Wiederholung] \alert{$\alpha^*$}
+\item[Wiederholung] \structure{$\alpha^*$}
 \end{description}
 \end{itemize}
 Analoge Sprachdefinition, z.b. $L(\alpha\beta) = L(\alpha)L(\beta)$
 \end{definition}
 \begin{example}
-$\alpha = (0|1)^*00$ \hfill $L(\alpha) = \left\{x \mid x \text{ Binärzahl}, x \mod 4 = 0 \right\}$
+\begin{itemize}
+\item $\alpha = (0|1)^*00$
+\item Worte bestehen aus einer beliebigen Folge von Einsen und Nullen gefolgt von zwei Nullen.
+\item $L(\alpha) \supseteq \left\{x \mid x \text{ Binärzahl}, x \mod 4 = 0 \right\}$
+\end{itemize}
 \end{example}
 \end{frame}
 }
 \defineUnit{automatenkonversionen}{%
 \draw[->] (k) edge node {$\epsilon$} (l);
 \end{tikzpicture}
 }\\
 \end{tabu}
 \end{frame}
-}
-\defineUnit{rezuenfazwei}{%
 \begin{frame}
 \frametitle{RE $\rightarrow$ $\epsilon$-NFA}
 \setbeamercovered{dynamic}
 \begin{tabu} to \linewidth {X}
 \node[tumgreen] () at (3.25, -1.7) {$N_\beta$};
 \node[state, initial] (i) at (0, 0) {};
 \node[state] (j) at (2.5, 1) {};
-\node[state, accepting] (k) at (4, 1) {};
+\node[state] (k) at (4, 1) {};
 \node[state] (l) at (2.5, -1) {};
-\node[state, accepting] (m) at (4, -1) {};
+\node[state] (m) at (4, -1) {};
+\node[state, accepting] (n) at (6.5, 0) {};
 \draw[->] (i) edge node {$\epsilon$} (j);
 \draw[->] (i) edge node {$\epsilon$} (l);
+\draw[->] (k) edge node {$\epsilon$} (n);
+\draw[->] (m) edge node {$\epsilon$} (n);
 \end{tikzpicture} \\
 \vfill
 \alert{$\gamma = \alpha^*$} \\
 \centering
 \begin{tikzpicture}[automaton, small, bend angle=70]
 \draw[tumgreen, fill=tumgreen!20] (2, 1) rectangle (4.5, -1);
 \node[tumgreen] () at (3.25, -1.2) {$N_\alpha$};
-\node[state, initial, accepting] (i) at (0, 0) {};
+\node[state, initial] (i) at (0, 0) {};
 \node[state] (j) at (2.5, 0) {};
-\node[state, accepting] (k) at (4, 0.5) {};
+\node[state] (k) at (4, 0.5) {};
-\node[state, accepting] (m) at (4, -0.5) {};
+\node[state] (m) at (4, -0.5) {};
+\node[state, accepting] (n) at (6.5, 0) {};
 \draw[->] (i) edge node {$\epsilon$} (j);
+\draw[->] (i) edge[bend right=90] node {$\epsilon$} (n);
 \draw[->] (k) edge [bend right] node {$\epsilon$} (j);
 \draw[->] (m) edge [bend left] node[above] {$\epsilon$} (j);
+\draw[->] (k) edge node {$\epsilon$} (n);
+\draw[->] (m) edge node {$\epsilon$} (n);
 \end{tikzpicture}
 \end{tabu}
 \end{frame}
 }
 \begin{frame}
 \frametitle{Äquivalenzen}
 \setbeamercovered{dynamic}
 \begin{definition}[Äquivalente Worte]
-Jede Sprache $L \subseteq \Sigma^*$ induziert eine Äquivalenzrelation $\alert{\equiv_L \subseteq \Sigma^* \times \Sigma^*}$:
+Jede Sprache $L \subseteq \Sigma^*$ induziert eine \structure{Äquivalenzrelation $\equiv_L \subseteq \Sigma^* \times \Sigma^*$}
-\[
+\[ u \structure{\equiv_L} v \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{uw} \in L \Leftrightarrow \alert{vw} \in L\right) \]
-u \alert{\equiv_L} v \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{uw} \in L \Leftrightarrow \alert{vw} \in L\right)
-\]
 \end{definition}
 \vfill
 \pause
 \begin{definition}[Äquivalente Zustände]
-Zwei Zustände im DFA $A$ sind \alert{äquivalent} wenn sie die selbe Sprache akzeptieren.
+Zwei Zustände im DFA $A$ sind \structure{äquivalent} wenn sie die selbe Sprache akzeptieren.
+\[ p \structure{\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) \]
-\[
-p \alert{\equiv_A} q \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{\hat{\delta}(p, w)} \in F \Leftrightarrow \alert{\hat{\delta}(q, w)} \in F \right)
-\]
 \end{definition}
 \end{frame}
 }
 \defineUnit{unterscheidbarezustaende}{%
 \begin{frame}
 \frametitle{Unterscheidbare Zustände}
 \setbeamercovered{dynamic}
 \begin{definition}[Unterscheidbarkeit]
-Zwei Zustände sind \alert{unterscheidbar}, wenn sie unterschiedliche Sprachen akzeptieren.
+Zwei Zustände sind \structure{unterscheidbar}, wenn sie unterschiedliche Sprachen akzeptieren.
-\[
+\[ p \structure{\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) \]
-p \alert{\not\equiv_A} q \Longleftrightarrow \left( \exists w \in \Sigma^*. \hat{\delta}(p, w) \alert{\in} F \wedge \hat{\delta}(q, w) \alert{\not\in} F \right)
-\]
 \end{definition}
 \begin{theorem}
 Sind $\delta(p, a)$ und $\delta(q, a)$ unterscheidbar, dann auch $p$ und $q$.
 \end{theorem}
 \defineUnit{quotientenautomat}{%
 \begin{frame}[t]
 \frametitle{DFA minimieren}
 \setbeamercovered{dynamic}
-\begin{block}{Idee}
+\begin{block}{Quotientenautomat}
-Erzeuge den \alert{Quotientenautomaten}.
 \begin{enumerate}
 \item Entferne alle von $q_0$ \alert{nicht erreichbaren} Zustände
 \item<1, 3-> Berechne die \alert{unterscheidbaren} Zustände
 \item<1, 6-> \alert{Kollabiere} die äquivalenten Zustände
 \end{enumerate}

Mercurial > 14ss.theoinf

comparison notes/tex/automatons.tex @ 13:834da46b1edb