Mercurial > 13ss.theoinf
diff notes/tex/ue04_notes.tex @ 44:15351d87ce76
transition notes
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Thu, 11 Jul 2013 22:06:26 +0200 |
parents | 90ffda7e20c7 |
children |
line wrap: on
line diff
--- a/notes/tex/ue04_notes.tex Thu Jul 11 21:57:50 2013 +0200 +++ b/notes/tex/ue04_notes.tex Thu Jul 11 22:06:26 2013 +0200 @@ -1,126 +1,13 @@ \input{preamble.tex} +\input{frames.tex} \title{Übung 4: Minimale DFAs} \subtitle{Theoretische Informatik Sommersemester 2013} \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} \begin{document} - -\begin{frame} - \titlepage -\end{frame} - -\begin{frame} - \frametitle{Äquivalenzen} - \setbeamercovered{dynamic} - - \begin{definition}[Äquivalente Worte] - Jede Sprache $L \subseteq \Sigma^*$ induziert eine Äquivalenzrelation $\alert{\equiv_L \subseteq \Sigma^* \times \Sigma^*}$: - \[ - u \alert{\equiv_L} v \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{uw} \in L \Leftrightarrow \alert{vw} \in L\right) - \] - \end{definition} - - \vfill - - \pause - - \begin{definition}[Äquivalente Zustände] - Zwei Zustände im DFA $A$ sind \alert{äquivalent} wenn sie die selbe Sprache akzeptieren. - - \[ - p \alert{\equiv_A} q \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{\hat{\delta}(p, w)} \in F \Leftrightarrow \alert{\hat{\delta}(q, w)} \in F \right) - \] - \end{definition} -\end{frame} - -\begin{frame} - \frametitle{Unterscheidbare Zustände} - \setbeamercovered{dynamic} - - \begin{definition}[Unterscheidbarkeit] - Zwei Zustände sind \alert{unterscheidbar}, wenn sie unterschiedliche Sprachen akzeptieren. - \[ - p \alert{\not\equiv_A} q \Longleftrightarrow \left( \exists w \in \Sigma^*. \hat{\delta}(p, w) \alert{\in} F \wedge \hat{\delta}(q, w) \alert{\not\in} F \right) - \] - \end{definition} - - \begin{theorem} - Sind $\delta(p, a)$ und $\delta(q, a)$ unterscheidbar, dann auch $p$ und $q$. - \end{theorem} - - \pause - - \begin{tikzpicture}[automaton, bend angle=40, node distance=2.5cm] - \node[state, initial] (q0) {$q_0$}; - \node[state] (q1) [right of = q0] {$q_1$}; - \node[state] (q2) [right of = q1] {$q_2$}; - \node[state, accepting] (q3) [right of = q2] {$q_3$}; - - \draw[->] (q0) edge node {$a$} (q1); - \draw[->] (q0) edge [bend left] node {$b$} (q2); - \draw[->] (q1) edge node {$a$} (q2); - \draw[->] (q1) edge [bend right] node {$b$} (q3); - \draw[->] (q2) edge node {$a,b$} (q3); - \draw[->] (q3) edge [loop right] node {$a,b$} (q3); - - \node<3>[state, fill=tumred!35] () at (q2) {$q_2$}; - \node<3->[state, accepting, fill=tumgreen!35] () at (q3) {$q_3$}; - - \node<4>[state, fill=tumred!35] () at (q0) {$q_0$}; - \node<4>[state, fill=tumred!35] () at (q1) {$q_1$}; - \draw<4>[->, tumred] (q0) edge [bend left] node {$b$} (q2); - \draw<4>[->, tumgreen] (q1) edge [bend right] node {$b$} (q3); - \end{tikzpicture} -\end{frame} - -\begin{frame}[t] - \frametitle{DFA minimieren} - \setbeamercovered{dynamic} - - \begin{block}{Idee} - Erzeuge den \alert{Quotientenautomaten}. - \begin{enumerate} - \item Entferne alle von $q_0$ \alert{nicht erreichbaren} Zustände - \item<1, 3-> Berechne die \alert{unterscheidbaren} Zustände - \item<1, 6-> \alert{Kollabiere} die äquivalenten Zustände - \end{enumerate} - \end{block} - - \vfill - - \begin{columns}[c]<2-> - \begin{column}{.5\textwidth}<3-> - \begin{center} - \begin{tabu}to .8\textwidth{|X[c]|X[c]|X[c]|X} - \multicolumn{2}{l}{0} \\ \tabucline{1-1} - \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} & \multicolumn{2}{l}{1} \\ \tabucline{1-2} - \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} & & \multicolumn{2}{l}{2} \\ \tabucline{1-3} - \alt<-3>{}{\textcolor{tumred}{$\times$}} & \alt<-3>{}{\textcolor{tumred}{$\times$}}& \alt<-3>{} {\textcolor{tumred}{$\times$}}& 3 \\ \tabucline{1-3} - \end{tabu} - \end{center} - \end{column} - \begin{column}{.5\textwidth} - \begin{tikzpicture}[automaton, node distance=2.5cm] - \useasboundingbox (-0.5, -0.5) rectangle (2, -2); - - \node[state, initial] (q0) {$q_0$}; - \node<-5>[state] (q1) [right of = q0] {$q_1$}; - \node<-5>[state] (q2) [below of = q0] {$q_2$}; - \node<6>[state, fill=tumred!40] (q12) [right of = q0] {$q_{12}$}; - \node[state, accepting] (q3) [right of = q2] {$q_3$}; - - \draw<-5>[->] (q0) edge node {$a$} (q1); - \draw<-5>[->] (q0) edge node {$b$} (q2); - \draw<-5>[->] (q1) edge node {$a,b$} (q3); - \draw<-5>[->] (q2) edge node {$a,b$} (q3); - \draw[->] (q3) edge [loop right] node [above] {$a,b$} (q3); - - \draw<6>[->] (q12) edge node {$a,b$} (q3); - \draw<6>[->] (q0) edge node {$a,b$} (q12); - \end{tikzpicture} - \end{column} - \end{columns} -\end{frame} - +\showUnit{titel} +\showUnit{aequivalentezustaende} +\showUnit{unterscheidbarezustande} +\showUnit{quotientenautomat} \end{document}