Mercurial > 13ss.theoinf
view notes/tex/ue03_notes.tex @ 19:7f7aff440629
fix error in theorem
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Mon, 13 May 2013 23:18:29 +0200 |
parents | b85e7ade4a89 |
children | 95ca58a84257 |
line wrap: on
line source
\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 = AX \cup B \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}