13ss.theoinf: notes/tex/automatons.tex comparison

comparison notes/tex/automatons.tex @ 43:c14b92bfa07f

add missing slides; correct some errors

author	Markus Kaiser <markus.kaiser@in.tum.de>
date	Thu, 11 Jul 2013 21:57:50 +0200
parents	35e8bb96da7b
children	8e79d33bdece

comparison

equal deleted inserted replaced

-:35e8bb96da7b
+:c14b92bfa07f
 \end{tikzpicture}
 \end{center}
 \end{frame}
 }
-\defineUnit{rezunfa}{%
+\defineUnit{rezuenfa}{%
 \begin{frame}
 \frametitle{RE $\rightarrow$ $\epsilon$-NFA}
 \setbeamercovered{dynamic}
 \begin{block}{Idee (Kleene)}
 \end{frame}
 }
 \defineUnit{produktautomat}{%
 \begin{frame}
-\frametitle{produktautomat}
+\frametitle{Produktautomat}
 \setbeamercovered{dynamic}
 \begin{theorem}
-sind $m_1 = (q_1, \sigma, \delta_1, s_1, f_1)$ und $m_2 = (q_2, \sigma, \delta_2, s_2, f_2)$ dfas, dann ist der \alert{produkt-automat}
+Sind $M_1 = (Q_1, \Sigma, \delta_1, s_1, F_1)$ und $M_2 = (Q_2, \Sigma, \delta_2, s_2, F_2)$ DFAs, dann ist der \alert{Produkt-Automat}
 \begin{align*}
-m &:= (\alert{q_1 \times q_2}, \sigma, \delta, (s_1, s_2), f_1 \times f_2) \\
+M &:= (\alert{Q_1 \times Q_2}, \Sigma, \delta, (s_1, s_2), F_1 \times F_2) \\
 \delta\left( (q_1, q_2), a \right) &:= \left( \alert{\delta_1}(q_1, a), \alert{\delta_2}(q_2, a) \right)
 \end{align*}
-ein dfa, der $l(m_1) \cap l(m_2)$ akzeptiert.
+ein DFA, der $L(M_1) \cap L(M_2)$ akzeptiert.
 \end{theorem}
 \end{frame}
 }
 \defineUnit{regexrechnen}{%
 \end{enumerate}
 \end{example}
 \end{frame}
 }
-\defineUnit{aequivalenteZustaende}{%
+\defineUnit{aequivalentezustaende}{%
 \begin{frame}
 \frametitle{Äquivalenzen}
 \setbeamercovered{dynamic}
 \begin{definition}[Äquivalente Worte]
 \]
 \end{definition}
 \end{frame}
 }
-\defineUnit{unterscheidbareZustaende}{%
+\defineUnit{unterscheidbarezustaende}{%
 \begin{frame}
 \frametitle{Unterscheidbare Zustände}
 \setbeamercovered{dynamic}
 \begin{definition}[Unterscheidbarkeit]
 \draw<4>[->, tumred] (q0) edge [bend left] node {$b$} (q2);
 \draw<4>[->, tumgreen] (q1) edge [bend right] node {$b$} (q3);
 \end{tikzpicture}
 \end{frame}
 }
+\defineUnit{quotientenautomat}{%
+\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}
+}
+\defineUnit{regulaeresprachen}{%
+\begin{frame}
+\frametitle{Reguläre Sprachen}
+\setbeamercovered{dynamic}
+\begin{center}
+\begin{tikzpicture}[node distance=2cm]
+\node (nfa) {NFA};
+\node (dfa) [left of=nfa] {DFA};
+\node (enfa) [right of=nfa] {$\epsilon$-NFA};
+\node (re) [below of=nfa] {RE};
+\draw [every edge] (nfa) -- (dfa);
+\draw [every edge] (enfa) -- (nfa);
+\draw [every edge] (dfa) -- (re);
+\draw [every edge] (nfa) -- (re);
+\draw [every edge] (re) -- (enfa);
+\end{tikzpicture}
+\end{center}
+\vfill
+\pause
+\begin{theorem}
+Für eine Darstellung $D$ einer regulären Sprache ist \alert{entscheidbar}:
+\vspace{1em}
+\begin{description}
+\item[Wortproblem] Gegeben $w$, gilt $w \in L(D)$?
+\item[Leerheitsproblem] Ist $L(D) = \emptyset$?
+\item[Endlichkeitsproblem] Ist $|L(D)| < \infty$?
+\item[Äquivalenzproblem] Gilt $L(D_1) = L(D_2)$?
+\end{description}
+\end{theorem}
+\end{frame}
+}

Mercurial > 13ss.theoinf

comparison notes/tex/automatons.tex @ 43:c14b92bfa07f