Mercurial > 13ss.theoinf

comparison notes/tex/ue03_notes.tex @ 15:b85e7ade4a89

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ue03 notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Mon, 06 May 2013 23:42:01 +0200
parents
children e639ca7b5478 7f7aff440629
comparison
equal deleted inserted replaced
14:4ea679e9e549 15:b85e7ade4a89
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}