changeset 9:f032a960b721

Automated merge with ssh://hg/13ss.theoinf
author Markus Kaiser <markus.kaiser@in.tum.de>
date Tue, 30 Apr 2013 01:32:17 +0200
parents a86f991f6290 (current diff) 2cabb8d02269 (diff)
children 5fc4bbf3ecc3
files
diffstat 4 files changed, 294 insertions(+), 3 deletions(-) [+]
line wrap: on
line diff
--- a/notes/tex/ue01_notes.tex	Thu Apr 25 18:26:02 2013 +0200
+++ b/notes/tex/ue01_notes.tex	Tue Apr 30 01:32:17 2013 +0200
@@ -30,7 +30,7 @@
 \tikzstyle{every edge} = [draw,very thick,->,>=latex]
 \tikzstyle{every state} = [circle,thick,draw,fill=tumblue!10]
 
-\title{Übung 1}
+\title{Übung 1: Sprachen und Automaten}
 \subtitle{Theoretische Informatik Sommersemester 2013}
 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
 
@@ -49,8 +49,8 @@
             \vfill
         \item Wann?
             \begin{itemize}
-                \item Dienstag 10-12h 00.08.038
-                \item Dienstag 12-14h 00.08.038
+                \item Dienstag 10:15-11:45 00.08.038
+                \item Dienstag 12:05-13:35 00.08.038
             \end{itemize}
         \item Übungsablauf, Aufgabentypen
         \item Hausaufgaben
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue02_notes.tex	Tue Apr 30 01:32:17 2013 +0200
@@ -0,0 +1,291 @@
+\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 2: Konversion RE $\rightarrow$ DFA}
+\subtitle{Theoretische Informatik Sommersemester 2013}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+
+\begin{frame}
+    \titlepage
+\end{frame}
+
+\begin{frame}
+    \setbeamercovered{dynamic}
+    \frametitle{Reguläre Ausdrücke}
+
+    \begin{definition}[Regulärer Ausdruck]
+        \alert{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 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^*$}
+                \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\}$
+    \end{example}
+\end{frame}
+
+\begin{frame}[c]
+    \setbeamercovered{dynamic}
+    \frametitle{Konversionen}
+
+    \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, tumred] (nfa) -- (dfa);
+            \draw [every edge, tumred] (enfa) -- (nfa);
+            \draw [every edge] (dfa) -- (re);
+            \draw [every edge] (nfa) -- (re);
+            \draw [every edge, tumred] (re) -- (enfa);
+        \end{tikzpicture}
+    \end{center}
+\end{frame}
+
+\begin{frame}
+    \setbeamercovered{dynamic}
+    \frametitle{RE $\rightarrow$ $\epsilon$-NFA}
+
+    \begin{block}{Idee (Kleene)}
+        Für einen Ausdruck \alert{$\gamma$} wird rekursiv mit struktureller Induktion ein $\epsilon$-NFA konstruiert.
+    \end{block}
+
+    \begin{tabu} to \linewidth {XXX}
+        \alert{$\gamma = \emptyset$} & \alert{$\gamma = \epsilon$} & \alert{$\gamma = a \in \Sigma$} \\
+        \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)]
+            \node[state, initial] () {};
+        \end{tikzpicture} &
+
+        \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)]
+            \node[state, initial, accepting] () {};
+        \end{tikzpicture} &
+
+        \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)]
+            \node[state, initial] (i) {};
+            \node[state, accepting] (j) [right of=i] {};
+
+            \draw[->] (i) edge node {$a$} (j);
+        \end{tikzpicture} \\
+        \vspace{2em}
+        \alert{$\gamma = \alpha\beta$} \\
+        \multicolumn3{c}{
+            \begin{tikzpicture}[automaton, small]
+                \draw[tumgreen, fill=tumgreen!20] (-0.3, 1) rectangle (1.8, -1);
+                \node[tumgreen] () at (0.75, -1.2) {$N_\alpha$};
+
+                \draw[tumgreen, fill=tumgreen!20] (3.7, 1) rectangle (5.8, -1);
+                \node[tumgreen] () at (4.75, -1.2) {$N_\beta$};
+
+                \node[state, initial] (i) at (0, 0) {};
+                \node[state] (j) at (1.5, 0.5) {};
+                \node[state] (k) at (1.5, -0.5) {};
+                \node[state] (l) at (4, 0) {};
+                \node[state, accepting] (m) at (5.5, 0) {};
+
+                \draw[->] (j) edge node {$\epsilon$} (l);
+                \draw[->] (k) edge node {$\epsilon$} (l);
+            \end{tikzpicture}
+        }\\
+    \end{tabu}
+\end{frame}
+
+\begin{frame}
+    \setbeamercovered{dynamic}
+    \frametitle{RE $\rightarrow$ $\epsilon$-NFA}
+
+    \begin{tabu} to \linewidth {X}
+        \alert{$\gamma = \alpha \mid \beta$} \\
+        \centering
+        \begin{tikzpicture}[automaton, small]
+            \draw[tumgreen, fill=tumgreen!20] (2, 1.5) rectangle (4.5, 0.5);
+            \node[tumgreen] () at (3.25, 0.3) {$N_\alpha$};
+
+            \draw[tumgreen, fill=tumgreen!20] (2, -0.5) rectangle (4.5, -1.5);
+            \node[tumgreen] () at (3.25, -1.7) {$N_\beta$};
+
+            \node[state, initial] (i) at (0, 0) {};
+
+            \node[state] (j) at (2.5, 1) {};
+            \node[state, accepting] (k) at (4, 1) {};
+            \node[state] (l) at (2.5, -1) {};
+            \node[state, accepting] (m) at (4, -1) {};
+
+            \draw[->] (i) edge node {$\epsilon$} (j);
+            \draw[->] (i) edge node {$\epsilon$} (l);
+        \end{tikzpicture} \\
+        \vfill
+
+        \alert{$\gamma = \alpha^*$} \\
+        \centering
+        \begin{tikzpicture}[automaton, small, bend angle=70]
+            \draw[tumgreen, fill=tumgreen!20] (2, 1) rectangle (4.5, -1);
+            \node[tumgreen] () at (3.25, -1.2) {$N_\alpha$};
+
+            \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) {};
+
+            \draw[->] (i) edge node {$\epsilon$} (j);
+            \draw[->] (k) edge [bend right] node {$\epsilon$} (j);
+            \draw[->] (m) edge [bend left] node[above] {$\epsilon$} (j);
+        \end{tikzpicture}
+    \end{tabu}
+\end{frame}
+
+\begin{frame}
+    \setbeamercovered{dynamic}
+    \frametitle{$\epsilon$-NFA $\rightarrow$ NFA}
+
+    \begin{block}{Idee}
+        Entferne $\epsilon$-Kanten durch das Bilden von $\epsilon$-Hüllen.
+        \begin{enumerate}
+            \item<1-> Entferne \alert{unnötige Knoten}.
+            \item<1,3-> Für jeden \alert{Pfad} der Form $\epsilon\ldots\epsilon \alert{a} \epsilon\ldots\epsilon$ verbinde Anfangs- und Endknoten mit einer \alert{$a$}-Kante.
+            \item<1,4-> Entferne alle \alert{$\epsilon$-Kanten} und unerreichbare Knoten.
+            \item<1,5-> Wurde das leere Wort akzeptiert mache den \alert{Anfangszustand} zum Endzustand.
+        \end{enumerate}
+    \end{block}
+
+    \vfill
+
+    \begin{tikzpicture}[automaton, bend angle=40, node distance=2.1cm]
+        \useasboundingbox (-1.4,2) rectangle (9, -2);
+
+        \node<-4>[state, initial] (q0) {$q_0$};
+        \node[state] (q2) [right = 3.2cm of q0] {$q_2$};
+        \node[state] (q3) [right of = q2] {$q_3$};
+        \node[state, accepting] (q4) [right of = q3] {$q_4$};
+
+        \draw[->] (q2) edge node {$0$} (q3);
+        \draw[->] (q3) edge node {$1$} (q4);
+
+        \draw<1-4>[->] (q3) edge [bend right] node [above] {$\epsilon$} (q2);
+        \draw[->] (q4) edge [bend right] node [above] {$1$} (q3);
+        \draw<1-4>[->] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4);
+
+        \node<1>[state] (q1) [right of = q0] {$q_1$};
+        \draw<1>[->] (q0) edge node {$\epsilon$} (q1);
+        \draw<1>[->] (q1) edge node {$1$} (q2);
+
+        \node<2>[state, fill=tumred!20] (q1) [right of = q0] {$q_1$};
+        \draw<2>[->, tumred] (q0) edge node {$\epsilon$} (q1);
+        \draw<2>[->, tumred] (q1) edge node {$0$} (q2);
+        \draw<2->[->, tumblue] (q0) edge [bend left] node {$0$} (q2);
+
+        \draw<3,4,5>[->, tumred] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4);
+        \draw<3>[->, tumred] (q4) edge [bend right] node [above] {$1$} (q3);
+        \draw<3,4>[->, tumred] (q3) edge [bend right] node [above] {$\epsilon$} (q2);
+        \draw<3->[->, tumgreen] (q0) edge node {$1$} (q2);
+
+        \draw<4->[->, tumgreen] (q2) edge [loop above] node [above] {$0$} (q2);
+        \draw<4->[->, tumgreen] (q3) edge [loop above] node [above] {$0$} (q3);
+        \draw<4->[->, tumgreen] (q4) edge [bend right=70] node [above] {$1$} (q2);
+
+        \node<5>[state, initial, accepting, fill=tumgreen!20] (q0) {$q_0$};
+
+        \node<6->[state, initial, accepting] (q0) {$q_0$};
+    \end{tikzpicture}
+\end{frame}
+
+\begin{frame}
+    \setbeamercovered{dynamic}
+    \frametitle{NFA $\rightarrow$ DFA}
+
+    \begin{block}{Idee (Potenzmengenkonstruktion)}
+        Konstruiere aus einem NFA $N = (Q, \Sigma, \delta, q_0, F)$ einen DFA $D = (P(Q), \Sigma, \overline{\delta}, \{q_0\}, F_M)$ mit Zuständen aus \alert{$P(Q)$}.
+
+        \begin{itemize}
+            \item $\overline{\delta}: \alert{P(Q)} \times \Sigma \mapsto P(Q)$ \\
+                \[\overline{\delta}(S, a) := \bigcup_{q \in S} \delta(q, a)\]
+            \item $F_M := \left\{S \subseteq Q \mid \alert{S \cap F} \neq \emptyset\right\}$
+        \end{itemize}
+    \end{block}
+
+    \begin{tikzpicture}[automaton, bend angle=20, node distance=2.1cm]
+        \useasboundingbox (-1.4,2) rectangle (9, -2);
+
+        \node[state, initial] (q0) {$q_0$};
+        \node[state, accepting] (q1) [right of = q0] {$q_1$};
+
+        \draw[->] (q0) edge [loop above] node {$0,1$} (q0);
+        \draw[->] (q0) edge node {$1$} (q1);
+
+        \node<2->(sep) [right of = q1] {$\rightarrow$};
+
+        \node<2->[state, initial, inner sep=1pt] (pq0) [right of = sep] {$q_{\{0\}}$};
+
+        \node<3->[state, accepting, inner sep=0pt] (pq01) [right of = pq0] {$q_{\{0,1\}}$};
+        \draw<3->[->] (pq0) edge [loop above] node {$0$} (pq0);
+        \draw<3->[->] (pq0) edge [bend left] node {$1$} (pq01);
+
+        \draw<4->[->] (pq01) edge [loop above] node {$1$} (pq01);
+        \draw<4->[->] (pq01) edge [bend left] node {$0$} (pq0);
+
+    \end{tikzpicture}
+\end{frame}
+
+\begin{frame}
+    \setbeamercovered{dynamic}
+    \frametitle{Produktautomat}
+    \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}
+
+        \begin{align*}
+            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.
+    \end{theorem}
+
+\end{frame}
+
+\end{document}
Binary file notes/ue01_notes.pdf has changed
Binary file notes/ue02_notes.pdf has changed