|
21
|
1 \documentclass[compress, german, t]{beamer} |
|
|
2 |
|
|
3 \usepackage[ngerman,english]{babel} |
|
|
4 \uselanguage{German} |
|
|
5 \languagepath{German} |
|
|
6 |
|
|
7 \usepackage[T1]{fontenc} |
|
|
8 \usepackage[utf8]{inputenc} |
|
|
9 |
|
|
10 \usepackage{helvet} |
|
|
11 \usepackage{url} |
|
|
12 \usepackage{listings} |
|
|
13 \usepackage{xcolor} |
|
|
14 \usepackage{tikz} |
|
|
15 \usepackage{pgfplots} |
|
|
16 \usetikzlibrary{automata} |
|
|
17 \usetikzlibrary{calc} |
|
|
18 \usetikzlibrary{shapes.geometric} |
|
|
19 \usetikzlibrary{positioning} |
|
|
20 \usepackage{tabu} |
|
|
21 |
|
|
22 \usepackage{beamerthemeLEA2} |
|
|
23 |
|
|
24 \newcommand{\N} {\mathbb{N}} % natürliche Zahlen |
|
|
25 \newcommand{\Z} {\mathbb{Z}} % ganze Zahlen |
|
|
26 \newcommand{\R} {\mathbb{R}} % reelle Zahlen |
|
|
27 \newcommand{\Prob} {\mathrm{P}} % Wahrscheinlichkeit |
|
|
28 \newcommand{\Oh} {\mathcal{O}} % O-Notation (Landau-Symbole) |
|
|
29 \newcommand{\mycite}[1]{\textcolor{tumgreen}{[#1]}} |
|
|
30 |
|
|
31 \tikzstyle{every edge} = [draw,very thick,->,>=latex] |
|
|
32 \tikzstyle{every state} = [circle,thick,draw,fill=tumblue!10] |
|
|
33 \tikzstyle{automaton} = [shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] |
|
|
34 \tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\LARGE] |
|
|
35 |
|
|
36 \title{Übung 4: Minimale DFAs} |
|
|
37 \subtitle{Theoretische Informatik Sommersemester 2013} |
|
|
38 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} |
|
|
39 |
|
|
40 \begin{document} |
|
|
41 |
|
|
42 \begin{frame} |
|
|
43 \titlepage |
|
|
44 \end{frame} |
|
|
45 |
|
|
46 \begin{frame} |
|
|
47 \frametitle{Äquivalenzen} |
|
|
48 \setbeamercovered{dynamic} |
|
|
49 |
|
|
50 \begin{definition}[Äquivalente Worte] |
|
|
51 Jede Sprache $L \subseteq \Sigma^*$ induziert eine Äquivalenzrelation $\alert{\equiv_L \subseteq \Sigma^* \times \Sigma^*}$: |
|
|
52 \[ |
|
|
53 u \alert{\equiv_L} v \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{uw} \in L \Leftrightarrow \alert{vw} \in L\right) |
|
|
54 \] |
|
|
55 \end{definition} |
|
|
56 |
|
|
57 \vfill |
|
|
58 |
|
|
59 \pause |
|
|
60 |
|
|
61 \begin{definition}[Äquivalente Zustände] |
|
|
62 Zwei Zustände im DFA $A$ sind \alert{äquivalent} wenn sie die selbe Sprache akzeptieren. |
|
|
63 |
|
|
64 \[ |
|
|
65 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) |
|
|
66 \] |
|
|
67 \end{definition} |
|
|
68 \end{frame} |
|
|
69 |
|
|
70 \begin{frame} |
|
|
71 \frametitle{Unterscheidbare Zustände} |
|
|
72 \setbeamercovered{dynamic} |
|
|
73 |
|
|
74 \begin{definition}[Unterscheidbarkeit] |
|
|
75 Zwei Zustände sind \alert{unterscheidbar}, wenn sie unterschiedliche Sprachen akzeptieren. |
|
|
76 \[ |
|
|
77 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) |
|
|
78 \] |
|
|
79 \end{definition} |
|
|
80 |
|
|
81 \begin{theorem} |
|
|
82 Sind $\delta(p, a)$ und $\delta(q, a)$ unterscheidbar, dann auch $p$ und $q$. |
|
|
83 \end{theorem} |
|
|
84 |
|
|
85 \pause |
|
|
86 |
|
|
87 \begin{tikzpicture}[automaton, bend angle=40, node distance=2.5cm] |
|
|
88 \node[state, initial] (q0) {$q_0$}; |
|
|
89 \node[state] (q1) [right of = q0] {$q_1$}; |
|
|
90 \node[state] (q2) [right of = q1] {$q_2$}; |
|
|
91 \node[state, accepting] (q3) [right of = q2] {$q_3$}; |
|
|
92 |
|
|
93 \draw[->] (q0) edge node {$a$} (q1); |
|
|
94 \draw[->] (q0) edge [bend left] node {$b$} (q2); |
|
|
95 \draw[->] (q1) edge node {$a$} (q2); |
|
|
96 \draw[->] (q1) edge [bend right] node {$b$} (q3); |
|
|
97 \draw[->] (q2) edge node {$a,b$} (q3); |
|
|
98 \draw[->] (q3) edge [loop right] node {$a,b$} (q3); |
|
|
99 |
|
|
100 \node<3>[state, fill=tumred!35] () at (q2) {$q_2$}; |
|
|
101 \node<3->[state, accepting, fill=tumgreen!35] () at (q3) {$q_3$}; |
|
|
102 |
|
|
103 \node<4>[state, fill=tumred!35] () at (q0) {$q_0$}; |
|
|
104 \node<4>[state, fill=tumred!35] () at (q1) {$q_1$}; |
|
|
105 \draw<4>[->, tumred] (q0) edge [bend left] node {$b$} (q2); |
|
|
106 \draw<4>[->, tumgreen] (q1) edge [bend right] node {$b$} (q3); |
|
|
107 \end{tikzpicture} |
|
|
108 \end{frame} |
|
|
109 |
|
|
110 \begin{frame}[t] |
|
|
111 \frametitle{DFA minimieren} |
|
|
112 \setbeamercovered{dynamic} |
|
|
113 |
|
|
114 \begin{block}{Idee} |
|
|
115 Erzeuge den \alert{Quotientenautomaten}. |
|
|
116 \begin{enumerate} |
|
|
117 \item Entferne alle von $q_0$ \alert{nicht erreichbaren} Zustände |
|
|
118 \item<1, 3-> Berechne die \alert{unterscheidbaren} Zustände |
|
|
119 \item<1, 6-> \alert{Kollabiere} die äquivalenten Zustände |
|
|
120 \end{enumerate} |
|
|
121 \end{block} |
|
|
122 |
|
|
123 \vfill |
|
|
124 |
|
|
125 \begin{columns}[c]<2-> |
|
|
126 \begin{column}{.5\textwidth}<3-> |
|
|
127 \begin{center} |
|
|
128 \begin{tabu}to .8\textwidth{|X[c]|X[c]|X[c]|X} |
|
|
129 \multicolumn{2}{l}{0} \\ \tabucline{1-1} |
|
|
130 \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} & \multicolumn{2}{l}{1} \\ \tabucline{1-2} |
|
|
131 \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} & & \multicolumn{2}{l}{2} \\ \tabucline{1-3} |
|
|
132 \alt<-3>{}{\textcolor{tumred}{$\times$}} & \alt<-3>{}{\textcolor{tumred}{$\times$}}& \alt<-3>{} {\textcolor{tumred}{$\times$}}& 3 \\ \tabucline{1-3} |
|
|
133 \end{tabu} |
|
|
134 \end{center} |
|
|
135 \end{column} |
|
|
136 \begin{column}{.5\textwidth} |
|
|
137 \begin{tikzpicture}[automaton, node distance=2.5cm] |
|
|
138 \useasboundingbox (-0.5, -0.5) rectangle (2, -2); |
|
|
139 |
|
|
140 \node[state, initial] (q0) {$q_0$}; |
|
|
141 \node<-5>[state] (q1) [right of = q0] {$q_1$}; |
|
|
142 \node<-5>[state] (q2) [below of = q0] {$q_2$}; |
|
|
143 \node<6>[state, fill=tumred!40] (q12) [right of = q0] {$q_{12}$}; |
|
|
144 \node[state, accepting] (q3) [right of = q2] {$q_3$}; |
|
|
145 |
|
|
146 \draw<-5>[->] (q0) edge node {$a$} (q1); |
|
|
147 \draw<-5>[->] (q0) edge node {$b$} (q2); |
|
|
148 \draw<-5>[->] (q1) edge node {$a,b$} (q3); |
|
|
149 \draw<-5>[->] (q2) edge node {$a,b$} (q3); |
|
|
150 \draw[->] (q3) edge [loop right] node [above] {$a,b$} (q3); |
|
28
|
151 |
|
21
|
152 \draw<6>[->] (q12) edge node {$a,b$} (q3); |
|
|
153 \draw<6>[->] (q0) edge node {$a,b$} (q12); |
|
|
154 \end{tikzpicture} |
|
|
155 \end{column} |
|
|
156 \end{columns} |
|
|
157 \end{frame} |
|
|
158 |
|
|
159 \end{document} |
