Mercurial > 13ss.theoinf

comparison notes/tex/ue03_notes.tex @ 44:15351d87ce76

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
transition notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Thu, 11 Jul 2013 22:06:26 +0200
parents 90ffda7e20c7
children
comparison
equal deleted inserted replaced
43:c14b92bfa07f 44:15351d87ce76
1 \input{preamble.tex} 1 \input{preamble.tex}
2 \input{frames.tex}
2 3
3 \title{Übung 3: Ardens- und Pumpinglemma} 4 \title{Übung 3: Ardens- und Pumpinglemma}
4 \subtitle{Theoretische Informatik Sommersemester 2013} 5 \subtitle{Theoretische Informatik Sommersemester 2013}
5 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} 6 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
6 7
7 \begin{document} 8 \begin{document}
8 9 \showUnit{titel}
9 \begin{frame} 10 \showUnit{regexrechnen}
10 \titlepage 11 \showUnit{arden}
11 \end{frame} 12 \showUnit{nfazure}
12 13 \showUnit{rpl}
13 \begin{frame} 14 \showUnit{rplanwenden}
14 \frametitle{Nochmal Reguläre Ausdrücke} 15 \showUnit{regulaeresprachen}
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 \[
43 X = AX \cup B \Longrightarrow X = A^* B
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}
174 Für eine Darstellung $D$ einer regulären Sprache ist \alert{entscheidbar}:
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} 16 \end{document}