# HG changeset patch # User Markus Kaiser # Date 1367876531 -7200 # Node ID 6113c7f0ad760e03bc64a1c465ea2981e0b2e80a # Parent 42bbfeddf8e9d108f50f2800ac5b6ac3dbde4122# Parent b85e7ade4a897724a4ae404dfc10673156d9c46b Automated merge with ssh://hg/13ss.theoinf diff -r 42bbfeddf8e9 -r 6113c7f0ad76 notes/tex/ue03_notes.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/ue03_notes.tex Mon May 06 23:42:11 2013 +0200 @@ -0,0 +1,228 @@ +\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 3: Ardens- und Pumpinglemma} +\subtitle{Theoretische Informatik Sommersemester 2013} +\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} + +\begin{document} + +\begin{frame} + \titlepage +\end{frame} + +\begin{frame}[c] + \frametitle{Feedback} + \setbeamercovered{dynamic} + \begin{itemize} + \item Hausaufgaben + \item Übungsniveau + \item Links + \end{itemize} +\end{frame} + +\begin{frame} + \frametitle{Nochmal Reguläre Ausdrücke} + \setbeamercovered{dynamic} + + \begin{theorem} + Die regulären Ausdrücke $\mathfrak{R}$ über einem Alphabet $\Sigma$ bilden mit Konkatenation $\circ$ und Veroderung $\mid$ einen \alert{Halbring} $\langle \mathfrak{R}, \mid, \circ, \emptyset, \epsilon \rangle$. + + \begin{itemize} + \item \alert{Assoziative} Operationen + \item Veroderung \alert{kommutativ} + \item \alert{Distributivität}: $\alpha (\beta \mid \gamma) \equiv \alpha\beta \mid \alpha\gamma$ + \item $\emptyset$ \alert{neutral} bezüglich Oder + \item $\epsilon$ \alert{neutral} bezüglich Konkatenation + \end{itemize} + \end{theorem} + + \begin{example} + \[ + 1\psi \mid 0\phi \mid \psi \equiv 0 \phi \mid (1 \mid \epsilon) \psi + \] + \end{example} +\end{frame} + +\begin{frame} + \frametitle{Ardens Lemma} + \setbeamercovered{dynamic} + + \begin{theorem}[Ardens Lemma] + Sind $A$, $B$ und $X$ Sprachen mit $\epsilon \not \in A$, dann gilt + \[ + X = AB \cup X \Longrightarrow X = A^* B + \] + Speziell gilt für reguläre Ausdrücke + \[ + X \equiv \alpha X \mid \beta \Longrightarrow X \equiv \alpha^* \beta + \] + \end{theorem} + + + \begin{example} + \[ + \psi \equiv 0 \psi \mid (1 \mid \epsilon) \phi \Longrightarrow \psi \equiv 0^*(1\mid \epsilon) \phi + \] + \end{example} +\end{frame} + +\begin{frame} + \frametitle{NFA $\rightarrow$ RE} + \setbeamercovered{dynamic} + + \begin{block}{Idee} + Erzeuge ein Gleichungssystem aus allen Zuständen. + \begin{enumerate} + \item<1,2-> Ausdruck für jeden Zustand + \item<1,3-> Auflösen nach $X_0$ mit Algebra und Ardens Lemma + \end{enumerate} + \end{block} + \begin{columns}<2-> + \begin{column}[b]{.65\textwidth} + \begin{align*} + X_0 &\equiv 1X_0 \mid 0X_1 \\ + &\equiv \uncover<4->{1X_0 \mid 00^*(\epsilon \mid 1X_0)} \\ + &\equiv \uncover<4->{(1 \mid 00^*1) X_0 \mid 00^*} \\ + &\equiv \uncover<4->{(1 \mid 00^*1)^*(00^*)} \\ + \\ + X_1 &\equiv 1X_0 \mid 0X_1 \alt<3->{\mid \epsilon}{\alert{\mid \epsilon}} \\ + &\equiv \uncover<3-> {0X_1 \mid (\epsilon \mid 1 X_0)}\\ + &\equiv \uncover<3-> {\alt<-2,4->{0^*(\epsilon \mid 1X_0)}{\alert{0^*(\epsilon \mid 1X_0)}}} + \end{align*} + \end{column} + \begin{column}[t]{.35\textwidth} + \begin{tikzpicture}[automaton] + \node[state, initial] (q0) {$q_0$}; + \node[state, accepting] (q1) [below of=q0] {$q_1$}; + + \draw[->] (q0) edge [bend right] node [left] {$0$} (q1); + \draw[->] (q1) edge [bend right] node [right] {$1$} (q0); + \draw[->] (q0) edge [loop right] node {$1$} (q0); + \draw[->] (q1) edge [loop right] node {$0$} (q1); + \end{tikzpicture} + \end{column} + \end{columns} +\end{frame} + +\begin{frame} + \frametitle{Pumping Lemma} + \setbeamercovered{dynamic} + + \begin{theorem}[Pumping Lemma für reguläre Sprachen] + Sei $R \subseteq \Sigma^*$ regulär. Dann gibt es ein $n > 0$, so dass sich \alert{jedes} $z \in R$ mit $|z| \geq n$ so in $z = uvw$ zerlegen lässt, dass + \begin{itemize} + \item $v \neq \epsilon$ + \item $|uv| \alert{\leq n}$ + \item $\forall i \alert{\geq 0}. uv^iw \in R$ + \end{itemize} + \end{theorem} + + \vfill + + \begin{center} + \begin{tikzpicture}[automaton] + \node[state, initial] (q0) {}; + \node[state, fill=tumred!20] (q1) [right of=q0] {}; + \node[state, accepting] (q2) [right of=q1] {}; + + + \draw[->, densely dashed] (q0) edge node {$u$} (q1); + \draw[->, tumred] (q1) edge [loop above] node {$v$} (q1); + \draw[->, densely dashed] (q1) edge node {$w$} (q2); + \end{tikzpicture} + \end{center} +\end{frame} + +\begin{frame} + \frametitle{Nichtregularität beweisen} + \setbeamercovered{dynamic} + + \begin{block}{Idee} + Gegenbeispiel fürs Pumpinglemma suchen. + \[ + \alert{\forall} n \in \N_0 \alert{\exists} z \in L. |z| \geq n \ \alert{\forall} u,v,w. \ z = uvw \ \text{\alert{nicht} pumpbar} + \] + \end{block} + + \vfill + + \begin{example}<2-> + Ist $L = \left\{ a^ib^i \mid i \in \N_0 \right\}$ regulär? + \begin{enumerate} + \item \alert{Sei $n$} PL-Zahl + \item \alert{Wähle} $\alert{z} = a^nb^n$ + \item Dann ist \alert{$z = uvw$} mit \alert{$|uv| \leq n$}, hier: $v=a^k$ mit $k > 0$ + \item Dann ist $uv^0w \not \in L$ + \item Damit ist L \alert{nicht} regulär. + \end{enumerate} + \end{example} +\end{frame} + +\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 reguläre Sprache $D$ 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} + +\end{document} diff -r 42bbfeddf8e9 -r 6113c7f0ad76 notes/ue03_notes.pdf Binary file notes/ue03_notes.pdf has changed diff -r 42bbfeddf8e9 -r 6113c7f0ad76 ue03.pdf Binary file ue03.pdf has changed diff -r 42bbfeddf8e9 -r 6113c7f0ad76 ue04.pdf Binary file ue04.pdf has changed