# HG changeset patch # User Markus Kaiser # Date 1399150183 -7200 # Node ID 834da46b1edbca18666ede84213ddb747b113e14 # Parent 11723d02ee58f2cb3436af3b73e72f0c2b48cc3f third sheet and notes diff -r 11723d02ee58 -r 834da46b1edb notes/tex/automatons.tex --- 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 diff -r 11723d02ee58 -r 834da46b1edb notes/tex/preamble.tex --- 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] diff -r 11723d02ee58 -r 834da46b1edb notes/tex/ue03_notes.tex --- /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} diff -r 11723d02ee58 -r 834da46b1edb notes/ue03_notes.pdf Binary file notes/ue03_notes.pdf has changed diff -r 11723d02ee58 -r 834da46b1edb ue03.pdf Binary file ue03.pdf has changed