|
31
|
1 \input{preamble.tex} |
|
21
|
2 |
|
|
3 \title{Übung 4: Minimale DFAs} |
|
|
4 \subtitle{Theoretische Informatik Sommersemester 2013} |
|
|
5 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} |
|
|
6 |
|
|
7 \begin{document} |
|
|
8 |
|
|
9 \begin{frame} |
|
|
10 \titlepage |
|
|
11 \end{frame} |
|
|
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); |
|
28
|
118 |
|
21
|
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} |
