Mercurial > 13ss.theoinf
comparison notes/tex/grammars.tex @ 41:5d10471f5585
move frame-definitions out of presentations
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Thu, 11 Jul 2013 20:42:36 +0200 |
parents | |
children | c14b92bfa07f |
comparison
equal
deleted
inserted
replaced
40:3175d3871752 | 41:5d10471f5585 |
---|---|
1 \defineUnit{grammatik}{% | |
2 \begin{frame} | |
3 \frametitle{Grammatiken} | |
4 \setbeamercovered{dynamic} | |
5 | |
6 \begin{definition}[Kontextfreie Grammatik] | |
7 Eine \alert{kontextfreie Grammatik} $G = (V, \Sigma, P, S)$ ist ein 4-Tupel: | |
8 \begin{description} | |
9 \item[V] endlich viele \alert{Nichtterminale} (Variablen) | |
10 \item[$\Sigma$] ein Alphabet von \alert{Terminalen} | |
11 \item[P] endlich viele \alert{Produktionen} $\subseteq V \times \left( V \cup \Sigma \right)^*$ | |
12 \item[S] ein \alert{Startsymbol} | |
13 \end{description} | |
14 \end{definition} | |
15 | |
16 \begin{example}[Vorbereitung 3] | |
17 $\Sigma = \left\{ 0, 1 \right\}$. Grammatik für alle Wörter ungerader Länge, bei denen alle Nullen vor der ersten Eins stehen und weniger Nullen als Einsen vorhanden sind. | |
18 \pause | |
19 \[ | |
20 S \rightarrow 0S1 \mid S11 \mid 1 | |
21 \] | |
22 \end{example} | |
23 \end{frame} | |
24 } | |
25 | |
26 \defineUnit{ableitung}{% | |
27 \begin{frame} | |
28 \frametitle{Ableitungsrelation} | |
29 \setbeamercovered{dynamic} | |
30 | |
31 \begin{definition}[Ableitungsrelation] | |
32 Eine CFG $G$ induziert eine \alert{Ableitungsrelation} $\rightarrow_G$ auf Wörtern über $V \cup \Sigma$: | |
33 \[ | |
34 \alpha \rightarrow_G \beta | |
35 \] | |
36 gdw es eine Regel $A \rightarrow \gamma$ in $P$ mit Wörtern $\alpha_1, \alpha_2$ gibt, so dass | |
37 \[ | |
38 \alpha = \alpha_1\alert{A}\alpha_2 \quad \text{und} \quad \beta = \alpha_1 \alert{\gamma} \alpha_2 | |
39 \] | |
40 \end{definition} | |
41 | |
42 \begin{example}[Vorbereitung 3] | |
43 Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$: | |
44 \begin{align*} | |
45 S &\rightarrow_G 0S1 \rightarrow_G 00S11 \rightarrow_G 00S1111 \rightarrow_G 0011111 \\ | |
46 \Rightarrow S &\rightarrow_G^* 0011111 | |
47 \end{align*} | |
48 \end{example} | |
49 \end{frame} | |
50 } | |
51 | |
52 \defineUnit{cfl}{% | |
53 \begin{frame}[c] | |
54 \frametitle{Kontextfreie Sprache} | |
55 \setbeamercovered{dynamic} | |
56 | |
57 \begin{definition}[Kontextfreie Sprache] | |
58 Eine kontextfreie Grammatik $G = (V, \Sigma, P, S)$ \alert{erzeugt} die Sprache | |
59 \[ | |
60 L(G) := \left\{ w \in \Sigma^* \mid S \rightarrow_G^* w \right\} | |
61 \] | |
62 Eine Sprache $L \subseteq \Sigma^*$ heißt \alert{kontextfrei} gdw es eine kontextfreie Grammatik $G$ gibt mit $L = L(G)$. | |
63 \end{definition} | |
64 \end{frame} | |
65 } | |
66 | |
67 \defineUnit{cnf}{% | |
68 \begin{frame} | |
69 \frametitle{CNF} | |
70 \setbeamercovered{dynamic} | |
71 | |
72 \begin{definition}[Chomsky-Normalform] | |
73 Eine kontextfreie Grammatik ist in \alert{Chomsky-Normalform} (CNF) genau dann wenn alle Produktionen die Form | |
74 \[ | |
75 A \rightarrow \alert{a} \quad \text{oder} \quad A \rightarrow \alert{BC} | |
76 \] | |
77 haben. | |
78 \end{definition} | |
79 | |
80 \vfill | |
81 | |
82 \begin{theorem} | |
83 Zu \alert{jeder} CFG $G$ existiert eine CFG $G'$ in Chomsky-Normalform mit | |
84 \[ | |
85 L(G') = L(G) \alert{\setminus \left\{ \epsilon \right\}} | |
86 \] | |
87 \end{theorem} | |
88 \end{frame} | |
89 } | |
90 | |
91 \defineUnit{cnfkonstruktion}{% | |
92 \begin{frame} | |
93 \frametitle{CNF Konstruktion} | |
94 \setbeamercovered{dynamic} | |
95 | |
96 \begin{block}{Idee} | |
97 Sei $G = (V, \Sigma, P, S)$ eine CFG. | |
98 \begin{enumerate} | |
99 \item<1,2-> Eliminiere \alert{$\epsilon$-Produktionen} | |
100 \item<1,3-> Eliminiere \alert{Kettenproduktionen} | |
101 \item<1,4-> \alert{Ersetze Terminale} durch Nichtterminale | |
102 \item<1,5-> \alert{Verkürze Ketten} von Nichtterminalen der Länge $\geq 3$ | |
103 \end{enumerate} | |
104 \end{block} | |
105 | |
106 \vspace{1em} | |
107 | |
108 \only<2> { | |
109 Sind \alert{$B \rightarrow \epsilon$} und \alert{$A \rightarrow \alpha B \beta$} in $P$, dann füge \alert{$A \rightarrow \alpha \beta$} hinzu. Entferne danach alle $\epsilon$-Produktionen. | |
110 \begin{align*} | |
111 S &\rightarrow Ab, \quad A \rightarrow aAA \mid \epsilon \\ | |
112 \intertext{neu:} | |
113 S &\rightarrow \alert{b} \\ | |
114 A &\rightarrow \alert{aA \mid a} | |
115 \end{align*} | |
116 } | |
117 | |
118 \only<3> { | |
119 Sind \alert{$A \rightarrow B$} und \alert{$B \rightarrow \alpha$} in $P$, dann füge \alert{$A \rightarrow \alpha$} hinzu. Entferne danach alle Kettenproduktionen und unerreichbaren Symbole. | |
120 \begin{align*} | |
121 S &\rightarrow A, \quad A \rightarrow a \mid B, \quad B \rightarrow bS \\ | |
122 \intertext{neu:} | |
123 A &\rightarrow \alert{a \mid bS} \\ | |
124 S &\rightarrow \alert{a \mid bS} | |
125 \end{align*} | |
126 } | |
127 | |
128 \only<4> { | |
129 Ersetze jedes \alert{$a \in \Sigma$} in einer rechten Seite \alert{länger als $1$} durch ein neues Nichtterminal. | |
130 \begin{align*} | |
131 S &\rightarrow aa \mid Bb \mid b, \quad B \rightarrow \ldots \\ | |
132 \intertext{neu:} | |
133 S &\rightarrow \alert{X_aX_a \mid BX_b \mid b} \\ | |
134 X_a &\rightarrow \alert{a}, \quad X_b \rightarrow \alert{b} | |
135 \end{align*} | |
136 } | |
137 | |
138 \only<5> { | |
139 Ersetze jede Produktion der Form $A \rightarrow B_1B_2\ldots B_k$ durch neue Nichtterminale mit Produktionen der Länge $2$. | |
140 \begin{align*} | |
141 S &\rightarrow X_aX_bBX_a, \quad X_a \rightarrow a, \quad X_b \rightarrow b, \quad B \rightarrow \ldots \\ | |
142 \intertext{neu:} | |
143 S &\rightarrow \alert{X_aT_1} \\ | |
144 T_1 &\rightarrow \alert{X_bT_2}, \quad T_2 \rightarrow \alert{BX_a} \\ | |
145 \end{align*} | |
146 } | |
147 \end{frame} | |
148 } | |
149 | |
150 \defineUnit{nuetzlichessymbol}{% | |
151 \begin{frame} | |
152 \frametitle{Eigenschaften von Symbolen} | |
153 \setbeamercovered{dynamic} | |
154 | |
155 \begin{definition} | |
156 Sei $G = (V, \Sigma, P, S)$ eine CFG. \\ | |
157 Ein Symbol $X \in V \cup \Sigma$ ist | |
158 \begin{description} | |
159 \item[nützlich] es gibt $S \rightarrow_G^* w \in \Sigma^*$ in der X \alert{vorkommt} | |
160 \item[erzeugend] es gibt $\alert{X} \rightarrow_G^* w \in \Sigma^*$ | |
161 \item[erreichbar] es gibt $S \rightarrow_G^* \alpha \alert{X} \beta$ | |
162 \end{description} | |
163 \end{definition} | |
164 | |
165 \vfill | |
166 | |
167 \begin{theorem} | |
168 Nützliche Symbole \alert{sind} erzeugend und erreichbar. Aber \alert{nicht} notwendigerweise umgekehrt. | |
169 \[ | |
170 S \rightarrow AB \mid a, \quad A \rightarrow b | |
171 \] | |
172 \end{theorem} | |
173 \end{frame} | |
174 } | |
175 | |
176 \defineUnit{cyk}{% | |
177 \begin{frame} | |
178 \frametitle{CYK} | |
179 \setbeamercovered{dynamic} | |
180 | |
181 \begin{definition}[Cocke-Younger-Kasami-Algorithmus] | |
182 Der \alert{CYK-Algorithmus} entscheidet das Wortproblem für kontextfreie Grammatiken in Chomsky-Normalform in $\Oh(n^3)$. \\ | |
183 Gegeben eine \alert{Grammatik} $G = (V, \Sigma, P, S)$ in CNF und ein \alert{Wort} $w = a_1 \ldots a_n \in \Sigma^*$. | |
184 Mit \[ V_{ij} := \left\{ A \in V \mid A \rightarrow_G^* \alert{a_i \ldots a_j} \right\}\] | |
185 ist \[ w \in L(G) \Leftrightarrow S \in V_{\alert{1n}} \] | |
186 \end{definition} | |
187 | |
188 \begin{align*} | |
189 V_{ii} &= \left\{ A \in V \mid (A \rightarrow a_i) \in P \right\} \\ | |
190 V_{ij} &= \left\{ A \in V \mid \exists k, B \in V_{ik}, C \in V_{k+1,j} \;.\; (A \rightarrow BC) \in P \right\} | |
191 \end{align*} | |
192 \end{frame} | |
193 } | |
194 | |
195 \defineUnit{cykbeispiel}{% | |
196 \begin{frame} | |
197 \frametitle{CYK} | |
198 \setbeamercovered{dynamic} | |
199 | |
200 \begin{block}{Idee} | |
201 Kombiniere \alert{Teilwörter} zum ganzen Wort, wenn möglich. | |
202 \begin{enumerate} | |
203 \item Initialisiere mit den \alert{$V_{ii}$}. | |
204 \item<3-5> Befülle die Tabelle von unten nach oben. | |
205 \end{enumerate} | |
206 \end{block} | |
207 | |
208 \[ S \rightarrow AB \mid BC, \quad A \rightarrow BA \mid a, \quad B \rightarrow CC \mid b, \quad C \rightarrow AB \mid a \] | |
209 \begin{center} | |
210 \extrarowsep=5pt | |
211 \begin{tabu}to .8\textwidth{r|X[c]|X[c]|X[c]|X[c]|} | |
212 \tabucline{2-2} | |
213 4 & \alt<-4>{}{$S,\ldots$} \\ \tabucline{2-3} | |
214 3 & \alt<-3>{}{$\emptyset$} & \alt<-3>{}{$S, A, C$} \\ \tabucline{2-4} | |
215 2 & \alt<-2>{}{$A$} & \alt<-2>{}{$B$} & \alt<-2>{}{$B$} \\ \tabucline{2-5} | |
216 1 & \alt<-1>{}{$B$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} \\ \tabucline{2-5} | |
217 \multicolumn{1}{r}{} & \multicolumn{1}{c}{\alert{b}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} \\ | |
218 \end{tabu} | |
219 \end{center} | |
220 \end{frame} | |
221 } | |
222 | |
223 \defineUnit{pda}{% | |
224 \begin{frame} | |
225 \frametitle{Kellerautomaten} | |
226 \setbeamercovered{dynamic} | |
227 | |
228 \begin{definition}[Kellerautomat] | |
229 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem | |
230 \begin{itemize} | |
231 \item endlichen Menge von \alert{Zuständen} $Q$ | |
232 \item endlichen \alert{Eingabealphabet} $\Sigma$ | |
233 \item endlichen \alert{Kelleralphabet} $\Gamma$ | |
234 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ | |
235 \item \alert{Startzustand} $q_0 \in Q$ | |
236 \item \alert{Kellerinitialisierung} $Z_0 \in \Gamma$ | |
237 \item Menge von \alert{Endzuständen} $F \subseteq Q$ | |
238 \end{itemize} | |
239 \end{definition} | |
240 | |
241 \begin{center} | |
242 \begin{tikzpicture}[automaton, node distance=4cm] | |
243 \node[state] (q0) {$q_i$}; | |
244 \node[state] (q1) [right of = q0] {$q_j$}; | |
245 | |
246 \draw[every edge] (q0) edge node {$a, X/\gamma$} (q1); | |
247 \end{tikzpicture} | |
248 \end{center} | |
249 \end{frame} | |
250 } | |
251 | |
252 \defineUnit{pdaakzeptanz}{% | |
253 \begin{frame} | |
254 \frametitle{Kellerautomaten} | |
255 \setbeamercovered{dynamic} | |
256 | |
257 \begin{definition}[Kellerautomat] | |
258 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem | |
259 \begin{itemize} | |
260 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ | |
261 \end{itemize} | |
262 \end{definition} | |
263 | |
264 \vfill | |
265 | |
266 \begin{definition}[Akzeptanz] | |
267 Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit Endzustand} gdw | |
268 \[ \exists \alert{f \in F}, \gamma \in \Gamma^*.(q_0, w, Z_0) \rightarrow_P^* (\alert{f}, \epsilon, \gamma) \] | |
269 Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit leerem Keller} gdw | |
270 \[ \exists q \in Q.(q_0, w, Z_0) \rightarrow_P^* (q, \epsilon, \alert{\epsilon}) \] | |
271 \end{definition} | |
272 \end{frame} | |
273 } | |
274 | |
275 \defineUnit{pdabeispiel}{% | |
276 \begin{frame} | |
277 \frametitle{Kellerautomaten} | |
278 \setbeamercovered{dynamic} | |
279 | |
280 \begin{definition}[Kellerautomat] | |
281 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem | |
282 \begin{itemize} | |
283 | |
284 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ | |
285 \end{itemize} | |
286 \end{definition} | |
287 | |
288 \vfill | |
289 | |
290 \begin{example}[] | |
291 PDA akzeptierend \alert{mit leerem Keller} zu $L = \left\{ a^nb^n \mid n \in \N \right\}$. | |
292 | |
293 \centering | |
294 \begin{tikzpicture}[automaton] | |
295 | |
296 \node[state, initial] (q0) {$q_0$}; | |
297 \node[state] (q1) [right of = q0] {$q_1$}; | |
298 | |
299 \draw[->] (q0) edge [bend left] node {$\epsilon, A/A$} (q1); | |
300 \draw[->] (q0) edge [bend right] node [below] {$\epsilon, Z_0/Z_0$} (q1); | |
301 | |
302 \draw[->] (q0) edge [loop above] node {$a, Z_0/AZ_0$} (q0); | |
303 \draw[->] (q0) edge [loop below] node {$a, A/AA$} (q0); | |
304 | |
305 \draw[->] (q1) edge [loop above] node {$b, A/\epsilon$} (q1); | |
306 \draw[->] (q1) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q1); | |
307 \end{tikzpicture} | |
308 \end{example} | |
309 \end{frame} | |
310 } |