Mercurial > 13ss.theoinf
comparison 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 |
comparison
equal
deleted
inserted
replaced
43:c14b92bfa07f | 44:15351d87ce76 |
---|---|
1 \input{preamble.tex} | 1 \input{preamble.tex} |
2 \input{frames.tex} | |
2 | 3 |
3 \title{Übung 4: Minimale DFAs} | 4 \title{Übung 4: Minimale DFAs} |
4 \subtitle{Theoretische Informatik Sommersemester 2013} | 5 \subtitle{Theoretische Informatik Sommersemester 2013} |
5 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} | 6 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} |
6 | 7 |
7 \begin{document} | 8 \begin{document} |
8 | 9 \showUnit{titel} |
9 \begin{frame} | 10 \showUnit{aequivalentezustaende} |
10 \titlepage | 11 \showUnit{unterscheidbarezustande} |
11 \end{frame} | 12 \showUnit{quotientenautomat} |
12 | |
13 \begin{frame} | |
14 \frametitle{Äquivalenzen} | |
15 \setbeamercovered{dynamic} | |
16 | |
17 \begin{definition}[Äquivalente Worte] | |
18 Jede Sprache $L \subseteq \Sigma^*$ induziert eine Äquivalenzrelation $\alert{\equiv_L \subseteq \Sigma^* \times \Sigma^*}$: | |
19 \[ | |
20 u \alert{\equiv_L} v \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{uw} \in L \Leftrightarrow \alert{vw} \in L\right) | |
21 \] | |
22 \end{definition} | |
23 | |
24 \vfill | |
25 | |
26 \pause | |
27 | |
28 \begin{definition}[Äquivalente Zustände] | |
29 Zwei Zustände im DFA $A$ sind \alert{äquivalent} wenn sie die selbe Sprache akzeptieren. | |
30 | |
31 \[ | |
32 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) | |
33 \] | |
34 \end{definition} | |
35 \end{frame} | |
36 | |
37 \begin{frame} | |
38 \frametitle{Unterscheidbare Zustände} | |
39 \setbeamercovered{dynamic} | |
40 | |
41 \begin{definition}[Unterscheidbarkeit] | |
42 Zwei Zustände sind \alert{unterscheidbar}, wenn sie unterschiedliche Sprachen akzeptieren. | |
43 \[ | |
44 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) | |
45 \] | |
46 \end{definition} | |
47 | |
48 \begin{theorem} | |
49 Sind $\delta(p, a)$ und $\delta(q, a)$ unterscheidbar, dann auch $p$ und $q$. | |
50 \end{theorem} | |
51 | |
52 \pause | |
53 | |
54 \begin{tikzpicture}[automaton, bend angle=40, node distance=2.5cm] | |
55 \node[state, initial] (q0) {$q_0$}; | |
56 \node[state] (q1) [right of = q0] {$q_1$}; | |
57 \node[state] (q2) [right of = q1] {$q_2$}; | |
58 \node[state, accepting] (q3) [right of = q2] {$q_3$}; | |
59 | |
60 \draw[->] (q0) edge node {$a$} (q1); | |
61 \draw[->] (q0) edge [bend left] node {$b$} (q2); | |
62 \draw[->] (q1) edge node {$a$} (q2); | |
63 \draw[->] (q1) edge [bend right] node {$b$} (q3); | |
64 \draw[->] (q2) edge node {$a,b$} (q3); | |
65 \draw[->] (q3) edge [loop right] node {$a,b$} (q3); | |
66 | |
67 \node<3>[state, fill=tumred!35] () at (q2) {$q_2$}; | |
68 \node<3->[state, accepting, fill=tumgreen!35] () at (q3) {$q_3$}; | |
69 | |
70 \node<4>[state, fill=tumred!35] () at (q0) {$q_0$}; | |
71 \node<4>[state, fill=tumred!35] () at (q1) {$q_1$}; | |
72 \draw<4>[->, tumred] (q0) edge [bend left] node {$b$} (q2); | |
73 \draw<4>[->, tumgreen] (q1) edge [bend right] node {$b$} (q3); | |
74 \end{tikzpicture} | |
75 \end{frame} | |
76 | |
77 \begin{frame}[t] | |
78 \frametitle{DFA minimieren} | |
79 \setbeamercovered{dynamic} | |
80 | |
81 \begin{block}{Idee} | |
82 Erzeuge den \alert{Quotientenautomaten}. | |
83 \begin{enumerate} | |
84 \item Entferne alle von $q_0$ \alert{nicht erreichbaren} Zustände | |
85 \item<1, 3-> Berechne die \alert{unterscheidbaren} Zustände | |
86 \item<1, 6-> \alert{Kollabiere} die äquivalenten Zustände | |
87 \end{enumerate} | |
88 \end{block} | |
89 | |
90 \vfill | |
91 | |
92 \begin{columns}[c]<2-> | |
93 \begin{column}{.5\textwidth}<3-> | |
94 \begin{center} | |
95 \begin{tabu}to .8\textwidth{|X[c]|X[c]|X[c]|X} | |
96 \multicolumn{2}{l}{0} \\ \tabucline{1-1} | |
97 \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} & \multicolumn{2}{l}{1} \\ \tabucline{1-2} | |
98 \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} & & \multicolumn{2}{l}{2} \\ \tabucline{1-3} | |
99 \alt<-3>{}{\textcolor{tumred}{$\times$}} & \alt<-3>{}{\textcolor{tumred}{$\times$}}& \alt<-3>{} {\textcolor{tumred}{$\times$}}& 3 \\ \tabucline{1-3} | |
100 \end{tabu} | |
101 \end{center} | |
102 \end{column} | |
103 \begin{column}{.5\textwidth} | |
104 \begin{tikzpicture}[automaton, node distance=2.5cm] | |
105 \useasboundingbox (-0.5, -0.5) rectangle (2, -2); | |
106 | |
107 \node[state, initial] (q0) {$q_0$}; | |
108 \node<-5>[state] (q1) [right of = q0] {$q_1$}; | |
109 \node<-5>[state] (q2) [below of = q0] {$q_2$}; | |
110 \node<6>[state, fill=tumred!40] (q12) [right of = q0] {$q_{12}$}; | |
111 \node[state, accepting] (q3) [right of = q2] {$q_3$}; | |
112 | |
113 \draw<-5>[->] (q0) edge node {$a$} (q1); | |
114 \draw<-5>[->] (q0) edge node {$b$} (q2); | |
115 \draw<-5>[->] (q1) edge node {$a,b$} (q3); | |
116 \draw<-5>[->] (q2) edge node {$a,b$} (q3); | |
117 \draw[->] (q3) edge [loop right] node [above] {$a,b$} (q3); | |
118 | |
119 \draw<6>[->] (q12) edge node {$a,b$} (q3); | |
120 \draw<6>[->] (q0) edge node {$a,b$} (q12); | |
121 \end{tikzpicture} | |
122 \end{column} | |
123 \end{columns} | |
124 \end{frame} | |
125 | |
126 \end{document} | 13 \end{document} |