Mercurial > 13ss.theoinf

comparison notes/tex/ue04_notes.tex @ 21:8b37b5ab61a5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ue04 notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Mon, 13 May 2013 23:19:33 +0200
parents
children fe6b8e2da038
comparison
equal deleted inserted replaced
20:8e82a6d407d3 21:8b37b5ab61a5
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);
151
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}