Mercurial > 13ss.theoinf
annotate 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 |
rev | line source |
---|---|
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 \[ | |
19
7f7aff440629
fix error in theorem
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
15
diff
changeset
|
86 X = AX \cup B \Longrightarrow X = A^* B |
15 | 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} |