# HG changeset patch # User Markus Kaiser # Date 1368479973 -7200 # Node ID 8b37b5ab61a5a6f3ef233eee02bebd926980d99f # Parent 8e82a6d407d351604b4dc7e18c6975d86e365f49 ue04 notes diff -r 8e82a6d407d3 -r 8b37b5ab61a5 notes/tex/ue04_notes.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/ue04_notes.tex Mon May 13 23:19:33 2013 +0200 @@ -0,0 +1,159 @@ +\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} diff -r 8e82a6d407d3 -r 8b37b5ab61a5 notes/ue04_notes.pdf Binary file notes/ue04_notes.pdf has changed