Mercurial > 14ss.theoinf

changeset 13:834da46b1edb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
third sheet and notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Sat, 03 May 2014 22:49:43 +0200
parents 11723d02ee58
children d5b561a49683
files notes/tex/automatons.tex notes/tex/preamble.tex notes/tex/ue03_notes.tex notes/ue03_notes.pdf ue03.pdf
diffstat 5 files changed, 56 insertions(+), 32 deletions(-) [+]
line wrap: on
line diff
--- a/notes/tex/automatons.tex	Mon Apr 28 12:27:03 2014 +0200
+++ b/notes/tex/automatons.tex	Sat May 03 22:49:43 2014 +0200
@@ -126,23 +126,27 @@
     \setbeamercovered{dynamic}
 
     \begin{definition}[Regulärer Ausdruck]
-        \alert{Reguläre Ausdrücke} sind induktiv definiert
+        \structure{Reguläre Ausdrücke} sind induktiv definiert
         \begin{itemize}
-            \item \alert{$\emptyset$} ist ein regulärer Ausdruck
-            \item \alert{$\epsilon$} ist ein regulärer Ausdruck
-            \item Für alle $a \in \Sigma$ ist \alert{$a$} ein regulärer Ausdruck
+            \item \structure{$\emptyset$} ist ein regulärer Ausdruck
+            \item \structure{$\epsilon$} ist ein regulärer Ausdruck
+            \item Für alle $a \in \Sigma$ ist \structure{$a$} ein regulärer Ausdruck
             \item Sind $\alpha$ und $\beta$ reguläre Ausdrücke, dann auch
-                \begin{description}
-                    \item[Konkatenation] \alert{$\alpha\beta$}
-                    \item[Veroderung] \alert{$\alpha \mid \beta$}
-                    \item[Wiederholung] \alert{$\alpha^*$}
+                \begin{description}[Konkatenation]
+                    \item[Konkatenation] \structure{$\alpha\beta$}
+                    \item[Veroderung] \structure{$\alpha \mid \beta$}
+                    \item[Wiederholung] \structure{$\alpha^*$}
                 \end{description}
         \end{itemize}
         Analoge Sprachdefinition, z.b. $L(\alpha\beta) = L(\alpha)L(\beta)$
     \end{definition}
 
     \begin{example}
-        $\alpha = (0|1)^*00$ \hfill $L(\alpha) = \left\{x \mid x \text{ Binärzahl}, x \mod 4 = 0 \right\}$
+        \begin{itemize}
+            \item $\alpha = (0|1)^*00$
+            \item Worte bestehen aus einer beliebigen Folge von Einsen und Nullen gefolgt von zwei Nullen.
+            \item $L(\alpha) \supseteq \left\{x \mid x \text{ Binärzahl}, x \mod 4 = 0 \right\}$
+        \end{itemize}
     \end{example}
 \end{frame}
 }
@@ -216,9 +220,7 @@
         }\\
     \end{tabu}
 \end{frame}
-}
 
-\defineUnit{rezuenfazwei}{%
 \begin{frame}
     \frametitle{RE $\rightarrow$ $\epsilon$-NFA}
     \setbeamercovered{dynamic}
@@ -236,12 +238,16 @@
             \node[state, initial] (i) at (0, 0) {};
 
             \node[state] (j) at (2.5, 1) {};
-            \node[state, accepting] (k) at (4, 1) {};
+            \node[state] (k) at (4, 1) {};
             \node[state] (l) at (2.5, -1) {};
-            \node[state, accepting] (m) at (4, -1) {};
+            \node[state] (m) at (4, -1) {};
+
+            \node[state, accepting] (n) at (6.5, 0) {};
 
             \draw[->] (i) edge node {$\epsilon$} (j);
             \draw[->] (i) edge node {$\epsilon$} (l);
+            \draw[->] (k) edge node {$\epsilon$} (n);
+            \draw[->] (m) edge node {$\epsilon$} (n);
         \end{tikzpicture} \\
         \vfill
 
@@ -251,15 +257,21 @@
             \draw[tumgreen, fill=tumgreen!20] (2, 1) rectangle (4.5, -1);
             \node[tumgreen] () at (3.25, -1.2) {$N_\alpha$};
 
-            \node[state, initial, accepting] (i) at (0, 0) {};
+            \node[state, initial] (i) at (0, 0) {};
 
             \node[state] (j) at (2.5, 0) {};
-            \node[state, accepting] (k) at (4, 0.5) {};
-            \node[state, accepting] (m) at (4, -0.5) {};
+            \node[state] (k) at (4, 0.5) {};
+            \node[state] (m) at (4, -0.5) {};
+
+            \node[state, accepting] (n) at (6.5, 0) {};
 
             \draw[->] (i) edge node {$\epsilon$} (j);
+            \draw[->] (i) edge[bend right=90] node {$\epsilon$} (n);
+
             \draw[->] (k) edge [bend right] node {$\epsilon$} (j);
             \draw[->] (m) edge [bend left] node[above] {$\epsilon$} (j);
+            \draw[->] (k) edge node {$\epsilon$} (n);
+            \draw[->] (m) edge node {$\epsilon$} (n);
         \end{tikzpicture}
     \end{tabu}
 \end{frame}
@@ -538,10 +550,8 @@
     \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)
-        \]
+        Jede Sprache $L \subseteq \Sigma^*$ induziert eine \structure{Äquivalenzrelation $\equiv_L \subseteq \Sigma^* \times \Sigma^*$}
+        \[ u \structure{\equiv_L} v \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{uw} \in L \Leftrightarrow \alert{vw} \in L\right) \]
     \end{definition}
 
     \vfill
@@ -549,11 +559,8 @@
     \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)
-        \]
+        Zwei Zustände im DFA $A$ sind \structure{äquivalent} wenn sie die selbe Sprache akzeptieren.
+        \[ p \structure{\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}
 }
@@ -564,10 +571,8 @@
     \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)
-        \]
+        Zwei Zustände sind \structure{unterscheidbar}, wenn sie unterschiedliche Sprachen akzeptieren.
+        \[ p \structure{\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}
@@ -605,8 +610,7 @@
     \frametitle{DFA minimieren}
     \setbeamercovered{dynamic}
 
-    \begin{block}{Idee}
-        Erzeuge den \alert{Quotientenautomaten}.
+    \begin{block}{Quotientenautomat}
         \begin{enumerate}
             \item Entferne alle von $q_0$ \alert{nicht erreichbaren} Zustände
             \item<1, 3-> Berechne die \alert{unterscheidbaren} Zustände
--- a/notes/tex/preamble.tex	Mon Apr 28 12:27:03 2014 +0200
+++ b/notes/tex/preamble.tex	Sat May 03 22:49:43 2014 +0200
@@ -70,7 +70,7 @@
 \tikzstyle{every edge} = [edge]
 \tikzstyle{every state} = [pretty]
 \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]
+\tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\Huge]
 
 \tikzstyle{every edge} = [edge]
 \tikzstyle{every state} = [pretty]
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue03_notes.tex	Sat May 03 22:49:43 2014 +0200
@@ -0,0 +1,20 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 3: Reguläre Ausdrücke und Minimalautomaten}
+\subtitle{Theoretische Informatik Sommersemester 2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{dfa}
+\showUnit{nfa}
+\showUnit{enfa}
+\showUnit{regex}
+\showUnit{rezuenfa}
+\showUnit{enfazunfa}
+\showUnit{nfazudfa}
+\showUnit{aequivalentezustaende}
+\showUnit{unterscheidbarezustaende}
+\showUnit{quotientenautomat}
+\end{document}
Binary file notes/ue03_notes.pdf has changed
Binary file ue03.pdf has changed