15
|
1 \documentclass[compress, german, t]{beamer} |
|
2 |
|
3 \usepackage[ngerman,english]{babel} |
|
4 \uselanguage{German} |
|
5 \languagepath{German} |
|
6 |
|
7 \usepackage[T1]{fontenc} |
|
8 \usepackage[utf8]{inputenc} |
|
9 |
|
10 \usepackage{helvet} |
|
11 \usepackage{url} |
|
12 \usepackage{listings} |
|
13 \usepackage{xcolor} |
|
14 \usepackage{tikz} |
|
15 \usepackage{pgfplots} |
|
16 \usetikzlibrary{automata} |
|
17 \usetikzlibrary{calc} |
|
18 \usetikzlibrary{shapes.geometric} |
|
19 \usetikzlibrary{positioning} |
|
20 \usepackage{tabu} |
|
21 |
|
22 \usepackage{beamerthemeLEA2} |
|
23 |
|
24 \newcommand{\N} {\mathbb{N}} % natürliche Zahlen |
|
25 \newcommand{\Z} {\mathbb{Z}} % ganze Zahlen |
|
26 \newcommand{\R} {\mathbb{R}} % reelle Zahlen |
|
27 \newcommand{\Prob} {\mathrm{P}} % Wahrscheinlichkeit |
|
28 \newcommand{\Oh} {\mathcal{O}} % O-Notation (Landau-Symbole) |
|
29 \newcommand{\mycite}[1]{\textcolor{tumgreen}{[#1]}} |
|
30 |
|
31 \tikzstyle{every edge} = [draw,very thick,->,>=latex] |
|
32 \tikzstyle{every state} = [circle,thick,draw,fill=tumblue!10] |
|
33 \tikzstyle{automaton} = [shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] |
|
34 \tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\LARGE] |
|
35 |
|
36 \title{Übung 3: Ardens- und Pumpinglemma} |
|
37 \subtitle{Theoretische Informatik Sommersemester 2013} |
|
38 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} |
|
39 |
|
40 \begin{document} |
|
41 |
|
42 \begin{frame} |
|
43 \titlepage |
|
44 \end{frame} |
|
45 |
|
46 \begin{frame}[c] |
|
47 \frametitle{Feedback} |
|
48 \setbeamercovered{dynamic} |
|
49 \begin{itemize} |
|
50 \item Hausaufgaben |
|
51 \item Übungsniveau |
|
52 \item Links |
|
53 \end{itemize} |
|
54 \end{frame} |
|
55 |
|
56 \begin{frame} |
|
57 \frametitle{Nochmal Reguläre Ausdrücke} |
|
58 \setbeamercovered{dynamic} |
|
59 |
|
60 \begin{theorem} |
|
61 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$. |
|
62 |
|
63 \begin{itemize} |
|
64 \item \alert{Assoziative} Operationen |
|
65 \item Veroderung \alert{kommutativ} |
|
66 \item \alert{Distributivität}: $\alpha (\beta \mid \gamma) \equiv \alpha\beta \mid \alpha\gamma$ |
|
67 \item $\emptyset$ \alert{neutral} bezüglich Oder |
|
68 \item $\epsilon$ \alert{neutral} bezüglich Konkatenation |
|
69 \end{itemize} |
|
70 \end{theorem} |
|
71 |
|
72 \begin{example} |
|
73 \[ |
|
74 1\psi \mid 0\phi \mid \psi \equiv 0 \phi \mid (1 \mid \epsilon) \psi |
|
75 \] |
|
76 \end{example} |
|
77 \end{frame} |
|
78 |
|
79 \begin{frame} |
|
80 \frametitle{Ardens Lemma} |
|
81 \setbeamercovered{dynamic} |
|
82 |
|
83 \begin{theorem}[Ardens Lemma] |
|
84 Sind $A$, $B$ und $X$ Sprachen mit $\epsilon \not \in A$, dann gilt |
|
85 \[ |
|
86 X = AB \cup X \Longrightarrow X = A^* B |
|
87 \] |
|
88 Speziell gilt für reguläre Ausdrücke |
|
89 \[ |
|
90 X \equiv \alpha X \mid \beta \Longrightarrow X \equiv \alpha^* \beta |
|
91 \] |
|
92 \end{theorem} |
|
93 |
|
94 |
|
95 \begin{example} |
|
96 \[ |
|
97 \psi \equiv 0 \psi \mid (1 \mid \epsilon) \phi \Longrightarrow \psi \equiv 0^*(1\mid \epsilon) \phi |
|
98 \] |
|
99 \end{example} |
|
100 \end{frame} |
|
101 |
|
102 \begin{frame} |
|
103 \frametitle{NFA $\rightarrow$ RE} |
|
104 \setbeamercovered{dynamic} |
|
105 |
|
106 \begin{block}{Idee} |
|
107 Erzeuge ein Gleichungssystem aus allen Zuständen. |
|
108 \begin{enumerate} |
|
109 \item<1,2-> Ausdruck für jeden Zustand |
|
110 \item<1,3-> Auflösen nach $X_0$ mit Algebra und Ardens Lemma |
|
111 \end{enumerate} |
|
112 \end{block} |
|
113 \begin{columns}<2-> |
|
114 \begin{column}[b]{.65\textwidth} |
|
115 \begin{align*} |
|
116 X_0 &\equiv 1X_0 \mid 0X_1 \\ |
|
117 &\equiv \uncover<4->{1X_0 \mid 00^*(\epsilon \mid 1X_0)} \\ |
|
118 &\equiv \uncover<4->{(1 \mid 00^*1) X_0 \mid 00^*} \\ |
|
119 &\equiv \uncover<4->{(1 \mid 00^*1)^*(00^*)} \\ |
|
120 \\ |
|
121 X_1 &\equiv 1X_0 \mid 0X_1 \alt<3->{\mid \epsilon}{\alert{\mid \epsilon}} \\ |
|
122 &\equiv \uncover<3-> {0X_1 \mid (\epsilon \mid 1 X_0)}\\ |
|
123 &\equiv \uncover<3-> {\alt<-2,4->{0^*(\epsilon \mid 1X_0)}{\alert{0^*(\epsilon \mid 1X_0)}}} |
|
124 \end{align*} |
|
125 \end{column} |
|
126 \begin{column}[t]{.35\textwidth} |
|
127 \begin{tikzpicture}[automaton] |
|
128 \node[state, initial] (q0) {$q_0$}; |
|
129 \node[state, accepting] (q1) [below of=q0] {$q_1$}; |
|
130 |
|
131 \draw[->] (q0) edge [bend right] node [left] {$0$} (q1); |
|
132 \draw[->] (q1) edge [bend right] node [right] {$1$} (q0); |
|
133 \draw[->] (q0) edge [loop right] node {$1$} (q0); |
|
134 \draw[->] (q1) edge [loop right] node {$0$} (q1); |
|
135 \end{tikzpicture} |
|
136 \end{column} |
|
137 \end{columns} |
|
138 \end{frame} |
|
139 |
|
140 \begin{frame} |
|
141 \frametitle{Pumping Lemma} |
|
142 \setbeamercovered{dynamic} |
|
143 |
|
144 \begin{theorem}[Pumping Lemma für reguläre Sprachen] |
|
145 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 |
|
146 \begin{itemize} |
|
147 \item $v \neq \epsilon$ |
|
148 \item $|uv| \alert{\leq n}$ |
|
149 \item $\forall i \alert{\geq 0}. uv^iw \in R$ |
|
150 \end{itemize} |
|
151 \end{theorem} |
|
152 |
|
153 \vfill |
|
154 |
|
155 \begin{center} |
|
156 \begin{tikzpicture}[automaton] |
|
157 \node[state, initial] (q0) {}; |
|
158 \node[state, fill=tumred!20] (q1) [right of=q0] {}; |
|
159 \node[state, accepting] (q2) [right of=q1] {}; |
|
160 |
|
161 |
|
162 \draw[->, densely dashed] (q0) edge node {$u$} (q1); |
|
163 \draw[->, tumred] (q1) edge [loop above] node {$v$} (q1); |
|
164 \draw[->, densely dashed] (q1) edge node {$w$} (q2); |
|
165 \end{tikzpicture} |
|
166 \end{center} |
|
167 \end{frame} |
|
168 |
|
169 \begin{frame} |
|
170 \frametitle{Nichtregularität beweisen} |
|
171 \setbeamercovered{dynamic} |
|
172 |
|
173 \begin{block}{Idee} |
|
174 Gegenbeispiel fürs Pumpinglemma suchen. |
|
175 \[ |
|
176 \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} |
|
177 \] |
|
178 \end{block} |
|
179 |
|
180 \vfill |
|
181 |
|
182 \begin{example}<2-> |
|
183 Ist $L = \left\{ a^ib^i \mid i \in \N_0 \right\}$ regulär? |
|
184 \begin{enumerate} |
|
185 \item \alert{Sei $n$} PL-Zahl |
|
186 \item \alert{Wähle} $\alert{z} = a^nb^n$ |
|
187 \item Dann ist \alert{$z = uvw$} mit \alert{$|uv| \leq n$}, hier: $v=a^k$ mit $k > 0$ |
|
188 \item Dann ist $uv^0w \not \in L$ |
|
189 \item Damit ist L \alert{nicht} regulär. |
|
190 \end{enumerate} |
|
191 \end{example} |
|
192 \end{frame} |
|
193 |
|
194 \begin{frame} |
|
195 \frametitle{Reguläre Sprachen} |
|
196 \setbeamercovered{dynamic} |
|
197 |
|
198 \begin{center} |
|
199 \begin{tikzpicture}[node distance=2cm] |
|
200 \node (nfa) {NFA}; |
|
201 \node (dfa) [left of=nfa] {DFA}; |
|
202 \node (enfa) [right of=nfa] {$\epsilon$-NFA}; |
|
203 \node (re) [below of=nfa] {RE}; |
|
204 |
|
205 \draw [every edge] (nfa) -- (dfa); |
|
206 \draw [every edge] (enfa) -- (nfa); |
|
207 \draw [every edge] (dfa) -- (re); |
|
208 \draw [every edge] (nfa) -- (re); |
|
209 \draw [every edge] (re) -- (enfa); |
|
210 \end{tikzpicture} |
|
211 \end{center} |
|
212 |
|
213 \vfill |
|
214 \pause |
|
215 |
|
216 \begin{theorem} |
|
217 Für eine reguläre Sprache $D$ ist \alert{entscheidbar}: |
|
218 \vspace{1em} |
|
219 \begin{description} |
|
220 \item[Wortproblem] Gegeben $w$, gilt $w \in L(D)$? |
|
221 \item[Leerheitsproblem] Ist $L(D) = \emptyset$? |
|
222 \item[Endlichkeitsproblem] Ist $|L(D)| < \infty$? |
|
223 \item[Äquivalenzproblem] Gilt $L(D_1) = L(D_2)$? |
|
224 \end{description} |
|
225 \end{theorem} |
|
226 \end{frame} |
|
227 |
|
228 \end{document} |