# HG changeset patch # User Markus Kaiser # Date 1367278337 -7200 # Node ID f032a960b7211a3b138b2255800adc8d31b350dc # Parent a86f991f62900c87a813df8bb92a4e5dacdba4f6# Parent 2cabb8d0226934eef2fba76ea46393a68f58e28f Automated merge with ssh://hg/13ss.theoinf diff -r a86f991f6290 -r f032a960b721 notes/tex/ue01_notes.tex --- 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 diff -r a86f991f6290 -r f032a960b721 notes/tex/ue02_notes.tex --- /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} diff -r a86f991f6290 -r f032a960b721 notes/ue01_notes.pdf Binary file notes/ue01_notes.pdf has changed diff -r a86f991f6290 -r f032a960b721 notes/ue02_notes.pdf Binary file notes/ue02_notes.pdf has changed