Mercurial > 13ss.theoinf
view notes/tex/ue04_notes.tex @ 28:fe6b8e2da038
ue07 notes
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Mon, 10 Jun 2013 23:21:11 +0200 |
parents | 8b37b5ab61a5 |
children | 90ffda7e20c7 |
line wrap: on
line source
\documentclass[compress, german, t]{beamer} \usepackage[ngerman,english]{babel} \uselanguage{German} \languagepath{German} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{helvet} \usepackage{url} \usepackage{listings} \usepackage{xcolor} \usepackage{tikz} \usepackage{pgfplots} \usetikzlibrary{automata} \usetikzlibrary{calc} \usetikzlibrary{shapes.geometric} \usetikzlibrary{positioning} \usepackage{tabu} \usepackage{beamerthemeLEA2} \newcommand{\N} {\mathbb{N}} % natürliche Zahlen \newcommand{\Z} {\mathbb{Z}} % ganze Zahlen \newcommand{\R} {\mathbb{R}} % reelle Zahlen \newcommand{\Prob} {\mathrm{P}} % Wahrscheinlichkeit \newcommand{\Oh} {\mathcal{O}} % O-Notation (Landau-Symbole) \newcommand{\mycite}[1]{\textcolor{tumgreen}{[#1]}} \tikzstyle{every edge} = [draw,very thick,->,>=latex] \tikzstyle{every state} = [circle,thick,draw,fill=tumblue!10] \tikzstyle{automaton} = [shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] \tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\LARGE] \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} \end{document}