Mercurial > 13ss.theoinf
annotate notes/tex/ue03_notes.tex @ 31:90ffda7e20c7
use common preamble
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Tue, 11 Jun 2013 16:21:06 +0200 |
| parents | 95ca58a84257 |
| children | 15351d87ce76 |
| rev | line source |
|---|---|
| 31 | 1 \input{preamble.tex} |
| 15 | 2 |
| 3 \title{Übung 3: Ardens- und Pumpinglemma} | |
| 4 \subtitle{Theoretische Informatik Sommersemester 2013} | |
| 5 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} | |
| 6 | |
| 7 \begin{document} | |
| 8 | |
| 9 \begin{frame} | |
| 10 \titlepage | |
| 11 \end{frame} | |
| 12 | |
| 13 \begin{frame} | |
| 14 \frametitle{Nochmal Reguläre Ausdrücke} | |
| 15 \setbeamercovered{dynamic} | |
| 16 | |
| 17 \begin{theorem} | |
| 18 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$. | |
| 19 | |
| 20 \begin{itemize} | |
| 21 \item \alert{Assoziative} Operationen | |
| 22 \item Veroderung \alert{kommutativ} | |
| 23 \item \alert{Distributivität}: $\alpha (\beta \mid \gamma) \equiv \alpha\beta \mid \alpha\gamma$ | |
| 24 \item $\emptyset$ \alert{neutral} bezüglich Oder | |
| 25 \item $\epsilon$ \alert{neutral} bezüglich Konkatenation | |
| 26 \end{itemize} | |
| 27 \end{theorem} | |
| 28 | |
| 29 \begin{example} | |
| 30 \[ | |
| 31 1\psi \mid 0\phi \mid \psi \equiv 0 \phi \mid (1 \mid \epsilon) \psi | |
| 32 \] | |
| 33 \end{example} | |
| 34 \end{frame} | |
| 35 | |
| 36 \begin{frame} | |
| 37 \frametitle{Ardens Lemma} | |
| 38 \setbeamercovered{dynamic} | |
| 39 | |
| 40 \begin{theorem}[Ardens Lemma] | |
| 41 Sind $A$, $B$ und $X$ Sprachen mit $\epsilon \not \in A$, dann gilt | |
| 42 \[ | |
|
19
7f7aff440629
fix error in theorem
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
15
diff
changeset
|
43 X = AX \cup B \Longrightarrow X = A^* B |
| 15 | 44 \] |
| 45 Speziell gilt für reguläre Ausdrücke | |
| 46 \[ | |
| 47 X \equiv \alpha X \mid \beta \Longrightarrow X \equiv \alpha^* \beta | |
| 48 \] | |
| 49 \end{theorem} | |
| 50 | |
| 51 | |
| 52 \begin{example} | |
| 53 \[ | |
| 54 \psi \equiv 0 \psi \mid (1 \mid \epsilon) \phi \Longrightarrow \psi \equiv 0^*(1\mid \epsilon) \phi | |
| 55 \] | |
| 56 \end{example} | |
| 57 \end{frame} | |
| 58 | |
| 59 \begin{frame} | |
| 60 \frametitle{NFA $\rightarrow$ RE} | |
| 61 \setbeamercovered{dynamic} | |
| 62 | |
| 63 \begin{block}{Idee} | |
| 64 Erzeuge ein Gleichungssystem aus allen Zuständen. | |
| 65 \begin{enumerate} | |
| 66 \item<1,2-> Ausdruck für jeden Zustand | |
| 67 \item<1,3-> Auflösen nach $X_0$ mit Algebra und Ardens Lemma | |
| 68 \end{enumerate} | |
| 69 \end{block} | |
| 70 \begin{columns}<2-> | |
| 71 \begin{column}[b]{.65\textwidth} | |
| 72 \begin{align*} | |
| 73 X_0 &\equiv 1X_0 \mid 0X_1 \\ | |
| 74 &\equiv \uncover<4->{1X_0 \mid 00^*(\epsilon \mid 1X_0)} \\ | |
| 75 &\equiv \uncover<4->{(1 \mid 00^*1) X_0 \mid 00^*} \\ | |
| 76 &\equiv \uncover<4->{(1 \mid 00^*1)^*(00^*)} \\ | |
| 77 \\ | |
| 78 X_1 &\equiv 1X_0 \mid 0X_1 \alt<3->{\mid \epsilon}{\alert{\mid \epsilon}} \\ | |
| 79 &\equiv \uncover<3-> {0X_1 \mid (\epsilon \mid 1 X_0)}\\ | |
| 80 &\equiv \uncover<3-> {\alt<-2,4->{0^*(\epsilon \mid 1X_0)}{\alert{0^*(\epsilon \mid 1X_0)}}} | |
| 81 \end{align*} | |
| 82 \end{column} | |
| 83 \begin{column}[t]{.35\textwidth} | |
| 84 \begin{tikzpicture}[automaton] | |
| 85 \node[state, initial] (q0) {$q_0$}; | |
| 86 \node[state, accepting] (q1) [below of=q0] {$q_1$}; | |
| 87 | |
| 88 \draw[->] (q0) edge [bend right] node [left] {$0$} (q1); | |
| 89 \draw[->] (q1) edge [bend right] node [right] {$1$} (q0); | |
| 90 \draw[->] (q0) edge [loop right] node {$1$} (q0); | |
| 91 \draw[->] (q1) edge [loop right] node {$0$} (q1); | |
| 92 \end{tikzpicture} | |
| 93 \end{column} | |
| 94 \end{columns} | |
| 95 \end{frame} | |
| 96 | |
| 97 \begin{frame} | |
| 98 \frametitle{Pumping Lemma} | |
| 99 \setbeamercovered{dynamic} | |
| 100 | |
| 101 \begin{theorem}[Pumping Lemma für reguläre Sprachen] | |
| 102 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 | |
| 103 \begin{itemize} | |
| 104 \item $v \neq \epsilon$ | |
| 105 \item $|uv| \alert{\leq n}$ | |
| 106 \item $\forall i \alert{\geq 0}. uv^iw \in R$ | |
| 107 \end{itemize} | |
| 108 \end{theorem} | |
| 109 | |
| 110 \vfill | |
| 111 | |
| 112 \begin{center} | |
| 113 \begin{tikzpicture}[automaton] | |
| 114 \node[state, initial] (q0) {}; | |
| 115 \node[state, fill=tumred!20] (q1) [right of=q0] {}; | |
| 116 \node[state, accepting] (q2) [right of=q1] {}; | |
| 117 | |
| 118 | |
| 119 \draw[->, densely dashed] (q0) edge node {$u$} (q1); | |
| 120 \draw[->, tumred] (q1) edge [loop above] node {$v$} (q1); | |
| 121 \draw[->, densely dashed] (q1) edge node {$w$} (q2); | |
| 122 \end{tikzpicture} | |
| 123 \end{center} | |
| 124 \end{frame} | |
| 125 | |
| 126 \begin{frame} | |
| 127 \frametitle{Nichtregularität beweisen} | |
| 128 \setbeamercovered{dynamic} | |
| 129 | |
| 130 \begin{block}{Idee} | |
| 131 Gegenbeispiel fürs Pumpinglemma suchen. | |
| 132 \[ | |
| 133 \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} | |
| 134 \] | |
| 135 \end{block} | |
| 136 | |
| 137 \vfill | |
| 138 | |
| 139 \begin{example}<2-> | |
| 140 Ist $L = \left\{ a^ib^i \mid i \in \N_0 \right\}$ regulär? | |
| 141 \begin{enumerate} | |
| 142 \item \alert{Sei $n$} PL-Zahl | |
| 143 \item \alert{Wähle} $\alert{z} = a^nb^n$ | |
| 144 \item Dann ist \alert{$z = uvw$} mit \alert{$|uv| \leq n$}, hier: $v=a^k$ mit $k > 0$ | |
| 145 \item Dann ist $uv^0w \not \in L$ | |
| 146 \item Damit ist L \alert{nicht} regulär. | |
| 147 \end{enumerate} | |
| 148 \end{example} | |
| 149 \end{frame} | |
| 150 | |
| 151 \begin{frame} | |
| 152 \frametitle{Reguläre Sprachen} | |
| 153 \setbeamercovered{dynamic} | |
| 154 | |
| 155 \begin{center} | |
| 156 \begin{tikzpicture}[node distance=2cm] | |
| 157 \node (nfa) {NFA}; | |
| 158 \node (dfa) [left of=nfa] {DFA}; | |
| 159 \node (enfa) [right of=nfa] {$\epsilon$-NFA}; | |
| 160 \node (re) [below of=nfa] {RE}; | |
| 161 | |
| 162 \draw [every edge] (nfa) -- (dfa); | |
| 163 \draw [every edge] (enfa) -- (nfa); | |
| 164 \draw [every edge] (dfa) -- (re); | |
| 165 \draw [every edge] (nfa) -- (re); | |
| 166 \draw [every edge] (re) -- (enfa); | |
| 167 \end{tikzpicture} | |
| 168 \end{center} | |
| 169 | |
| 170 \vfill | |
| 171 \pause | |
| 172 | |
| 173 \begin{theorem} | |
|
18
e639ca7b5478
remove feedback slide; correct errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
15
diff
changeset
|
174 Für eine Darstellung $D$ einer regulären Sprache ist \alert{entscheidbar}: |
| 15 | 175 \vspace{1em} |
| 176 \begin{description} | |
| 177 \item[Wortproblem] Gegeben $w$, gilt $w \in L(D)$? | |
| 178 \item[Leerheitsproblem] Ist $L(D) = \emptyset$? | |
| 179 \item[Endlichkeitsproblem] Ist $|L(D)| < \infty$? | |
| 180 \item[Äquivalenzproblem] Gilt $L(D_1) = L(D_2)$? | |
| 181 \end{description} | |
| 182 \end{theorem} | |
| 183 \end{frame} | |
| 184 | |
| 185 \end{document} |