Mercurial > 13ss.theoinf
annotate notes/tex/grammars.tex @ 43:c14b92bfa07f
add missing slides; correct some errors
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Thu, 11 Jul 2013 21:57:50 +0200 |
parents | 5d10471f5585 |
children | 72ac27051d7e |
rev | line source |
---|---|
41
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
1 \defineUnit{grammatik}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
2 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
3 \frametitle{Grammatiken} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
4 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
5 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
6 \begin{definition}[Kontextfreie Grammatik] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
7 Eine \alert{kontextfreie Grammatik} $G = (V, \Sigma, P, S)$ ist ein 4-Tupel: |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
8 \begin{description} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
9 \item[V] endlich viele \alert{Nichtterminale} (Variablen) |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
10 \item[$\Sigma$] ein Alphabet von \alert{Terminalen} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
11 \item[P] endlich viele \alert{Produktionen} $\subseteq V \times \left( V \cup \Sigma \right)^*$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
12 \item[S] ein \alert{Startsymbol} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
13 \end{description} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
14 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
15 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
16 \begin{example}[Vorbereitung 3] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
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. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
18 \pause |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
19 \[ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
20 S \rightarrow 0S1 \mid S11 \mid 1 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
21 \] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
22 \end{example} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
23 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
24 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
25 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
26 \defineUnit{ableitung}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
27 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
28 \frametitle{Ableitungsrelation} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
29 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
30 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
31 \begin{definition}[Ableitungsrelation] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
32 Eine CFG $G$ induziert eine \alert{Ableitungsrelation} $\rightarrow_G$ auf Wörtern über $V \cup \Sigma$: |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
33 \[ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
34 \alpha \rightarrow_G \beta |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
35 \] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
36 gdw es eine Regel $A \rightarrow \gamma$ in $P$ mit Wörtern $\alpha_1, \alpha_2$ gibt, so dass |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
37 \[ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
38 \alpha = \alpha_1\alert{A}\alpha_2 \quad \text{und} \quad \beta = \alpha_1 \alert{\gamma} \alpha_2 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
39 \] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
40 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
41 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
42 \begin{example}[Vorbereitung 3] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
43 Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$: |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
44 \begin{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
45 S &\rightarrow_G 0S1 \rightarrow_G 00S11 \rightarrow_G 00S1111 \rightarrow_G 0011111 \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
46 \Rightarrow S &\rightarrow_G^* 0011111 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
47 \end{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
48 \end{example} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
49 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
50 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
51 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
52 \defineUnit{cfl}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
53 \begin{frame}[c] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
54 \frametitle{Kontextfreie Sprache} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
55 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
56 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
57 \begin{definition}[Kontextfreie Sprache] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
58 Eine kontextfreie Grammatik $G = (V, \Sigma, P, S)$ \alert{erzeugt} die Sprache |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
59 \[ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
60 L(G) := \left\{ w \in \Sigma^* \mid S \rightarrow_G^* w \right\} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
61 \] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
62 Eine Sprache $L \subseteq \Sigma^*$ heißt \alert{kontextfrei} gdw es eine kontextfreie Grammatik $G$ gibt mit $L = L(G)$. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
63 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
64 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
65 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
66 |
43
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
67 \defineUnit{induktivesprachdefinition}{% |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
68 \begin{frame} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
69 \frametitle{Induktive Sprachdefinition} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
70 \setbeamercovered{dynamic} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
71 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
72 \begin{block}{Induktive Sprachdefinition} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
73 Die \alert{induktive Definition} ($\Longrightarrow$) erzeugt Wörter \alert{bottom-up}, setzt also kleine Wörter zu größeren zusammen. |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
74 \end{block} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
75 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
76 \begin{example}[Vorbereitung 3] |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
77 Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$: |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
78 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
79 \begin{align*} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
80 1 &\in L_G(S) \\ |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
81 u \in L_G(S) \quad \Longrightarrow \quad 0\alert{u}1 &\in L_G(S) \\ |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
82 u \in L_G(S) \quad \Longrightarrow \quad \alert{u}11 &\in L_G(S) |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
83 \end{align*} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
84 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
85 Also z.B: |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
86 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
87 \[ |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
88 1 \in L_G(S) \Longrightarrow 0\alert{1}0 \in L_G(S) \Longrightarrow \alert{010}11 \in L_G(S) |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
89 \] |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
90 \end{example} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
91 \end{frame} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
92 } |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
93 |
41
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
94 \defineUnit{cnf}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
95 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
96 \frametitle{CNF} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
97 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
98 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
99 \begin{definition}[Chomsky-Normalform] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
100 Eine kontextfreie Grammatik ist in \alert{Chomsky-Normalform} (CNF) genau dann wenn alle Produktionen die Form |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
101 \[ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
102 A \rightarrow \alert{a} \quad \text{oder} \quad A \rightarrow \alert{BC} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
103 \] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
104 haben. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
105 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
106 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
107 \vfill |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
108 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
109 \begin{theorem} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
110 Zu \alert{jeder} CFG $G$ existiert eine CFG $G'$ in Chomsky-Normalform mit |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
111 \[ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
112 L(G') = L(G) \alert{\setminus \left\{ \epsilon \right\}} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
113 \] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
114 \end{theorem} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
115 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
116 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
117 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
118 \defineUnit{cnfkonstruktion}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
119 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
120 \frametitle{CNF Konstruktion} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
121 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
122 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
123 \begin{block}{Idee} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
124 Sei $G = (V, \Sigma, P, S)$ eine CFG. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
125 \begin{enumerate} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
126 \item<1,2-> Eliminiere \alert{$\epsilon$-Produktionen} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
127 \item<1,3-> Eliminiere \alert{Kettenproduktionen} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
128 \item<1,4-> \alert{Ersetze Terminale} durch Nichtterminale |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
129 \item<1,5-> \alert{Verkürze Ketten} von Nichtterminalen der Länge $\geq 3$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
130 \end{enumerate} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
131 \end{block} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
132 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
133 \vspace{1em} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
134 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
135 \only<2> { |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
136 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. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
137 \begin{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
138 S &\rightarrow Ab, \quad A \rightarrow aAA \mid \epsilon \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
139 \intertext{neu:} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
140 S &\rightarrow \alert{b} \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
141 A &\rightarrow \alert{aA \mid a} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
142 \end{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
143 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
144 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
145 \only<3> { |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
146 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. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
147 \begin{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
148 S &\rightarrow A, \quad A \rightarrow a \mid B, \quad B \rightarrow bS \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
149 \intertext{neu:} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
150 A &\rightarrow \alert{a \mid bS} \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
151 S &\rightarrow \alert{a \mid bS} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
152 \end{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
153 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
154 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
155 \only<4> { |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
156 Ersetze jedes \alert{$a \in \Sigma$} in einer rechten Seite \alert{länger als $1$} durch ein neues Nichtterminal. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
157 \begin{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
158 S &\rightarrow aa \mid Bb \mid b, \quad B \rightarrow \ldots \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
159 \intertext{neu:} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
160 S &\rightarrow \alert{X_aX_a \mid BX_b \mid b} \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
161 X_a &\rightarrow \alert{a}, \quad X_b \rightarrow \alert{b} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
162 \end{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
163 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
164 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
165 \only<5> { |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
166 Ersetze jede Produktion der Form $A \rightarrow B_1B_2\ldots B_k$ durch neue Nichtterminale mit Produktionen der Länge $2$. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
167 \begin{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
168 S &\rightarrow X_aX_bBX_a, \quad X_a \rightarrow a, \quad X_b \rightarrow b, \quad B \rightarrow \ldots \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
169 \intertext{neu:} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
170 S &\rightarrow \alert{X_aT_1} \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
171 T_1 &\rightarrow \alert{X_bT_2}, \quad T_2 \rightarrow \alert{BX_a} \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
172 \end{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
173 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
174 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
175 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
176 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
177 \defineUnit{nuetzlichessymbol}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
178 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
179 \frametitle{Eigenschaften von Symbolen} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
180 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
181 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
182 \begin{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
183 Sei $G = (V, \Sigma, P, S)$ eine CFG. \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
184 Ein Symbol $X \in V \cup \Sigma$ ist |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
185 \begin{description} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
186 \item[nützlich] es gibt $S \rightarrow_G^* w \in \Sigma^*$ in der X \alert{vorkommt} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
187 \item[erzeugend] es gibt $\alert{X} \rightarrow_G^* w \in \Sigma^*$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
188 \item[erreichbar] es gibt $S \rightarrow_G^* \alpha \alert{X} \beta$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
189 \end{description} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
190 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
191 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
192 \vfill |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
193 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
194 \begin{theorem} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
195 Nützliche Symbole \alert{sind} erzeugend und erreichbar. Aber \alert{nicht} notwendigerweise umgekehrt. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
196 \[ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
197 S \rightarrow AB \mid a, \quad A \rightarrow b |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
198 \] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
199 \end{theorem} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
200 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
201 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
202 |
43
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
203 \defineUnit{cfpl}{% |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
204 \begin{frame} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
205 \frametitle{Pumping Lemma für CFLs} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
206 \setbeamercovered{dynamic} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
207 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
208 \begin{theorem}[Pumping Lemma für kontextfreie Sprachen] |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
209 Sei $L \subseteq \Sigma^*$ kontextfrei. Dann gibt es ein $n > 0$, so dass sich \alert{jedes} $z \in L$ mit $|z| \geq n$ so in \alert{$z = uvwxy$} zerlegen lässt, dass |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
210 \begin{itemize} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
211 \item $vx \alert{\neq \epsilon}$ |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
212 \item $|vwx| \alert{\leq n}$ |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
213 \item $\forall i \alert{\geq 0}. uv^iwx^iy \in L$ |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
214 \end{itemize} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
215 \end{theorem} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
216 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
217 \vfill |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
218 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
219 \begin{center} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
220 \begin{columns} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
221 \begin{column}{.4\textwidth} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
222 \begin{tikzpicture} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
223 \coordinate (outer) at (2, 2.4); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
224 \coordinate (middle) at (2.2, 1.2); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
225 \coordinate (inner) at (2.2, 0.6); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
226 % outer |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
227 \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
228 % middle |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
229 \draw[fill=tumgreen!40] (1.2, 0) -- (1.7, 0) -- (inner) -- (2.7, 0) -- (3.2, 0) -- (middle) -- (1.2, 0); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
230 % inner |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
231 \draw[fill=tumblue!40] (1.7, 0) -- (inner) -- (2.7, 0) -- (1.7, 0); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
232 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
233 % path |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
234 \draw[dashed, thick] (outer) -- (middle) -- (inner); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
235 \draw[fill] (outer) circle (1pt); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
236 \draw[fill] (middle) circle (1pt); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
237 \draw[fill] (inner) circle (1pt); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
238 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
239 % nodes |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
240 \node[below] at (0.6, 0) {$u$}; |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
241 \node[below] at (1.45, 0) {$v$}; |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
242 \node[below] at (2.2, 0) {$w$}; |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
243 \node[below] at (2.95, 0) {$x$}; |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
244 \node[below] at (3.6, 0) {$y$}; |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
245 \end{tikzpicture} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
246 \end{column} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
247 \begin{column}{.4\textwidth} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
248 \begin{tikzpicture} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
249 \coordinate (outer) at (2, 2.4); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
250 \coordinate (middle) at (2.2, 1.2); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
251 \coordinate (inner) at (2.2, 0.6); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
252 % outer |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
253 \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
254 % inner |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
255 \draw[fill=tumblue!40] (1.7, 0.6) -- (middle) -- (2.7, 0.6) -- (1.7, 0.6); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
256 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
257 % path |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
258 \draw[dashed, thick] (outer) -- (middle); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
259 \draw[fill] (outer) circle (1pt); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
260 \draw[fill] (middle) circle (1pt); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
261 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
262 % nodes |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
263 \node[below] at (0.6, 0) {$u$}; |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
264 \node[below] at (2.2, 0) {$w$}; |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
265 \node[below] at (3.6, 0) {$y$}; |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
266 \end{tikzpicture} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
267 \end{column} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
268 \end{columns} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
269 \end{center} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
270 \end{frame} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
271 } |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
272 |
41
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
273 \defineUnit{cyk}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
274 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
275 \frametitle{CYK} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
276 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
277 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
278 \begin{definition}[Cocke-Younger-Kasami-Algorithmus] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
279 Der \alert{CYK-Algorithmus} entscheidet das Wortproblem für kontextfreie Grammatiken in Chomsky-Normalform in $\Oh(n^3)$. \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
280 Gegeben eine \alert{Grammatik} $G = (V, \Sigma, P, S)$ in CNF und ein \alert{Wort} $w = a_1 \ldots a_n \in \Sigma^*$. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
281 Mit \[ V_{ij} := \left\{ A \in V \mid A \rightarrow_G^* \alert{a_i \ldots a_j} \right\}\] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
282 ist \[ w \in L(G) \Leftrightarrow S \in V_{\alert{1n}} \] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
283 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
284 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
285 \begin{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
286 V_{ii} &= \left\{ A \in V \mid (A \rightarrow a_i) \in P \right\} \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
287 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\} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
288 \end{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
289 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
290 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
291 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
292 \defineUnit{cykbeispiel}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
293 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
294 \frametitle{CYK} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
295 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
296 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
297 \begin{block}{Idee} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
298 Kombiniere \alert{Teilwörter} zum ganzen Wort, wenn möglich. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
299 \begin{enumerate} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
300 \item Initialisiere mit den \alert{$V_{ii}$}. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
301 \item<3-5> Befülle die Tabelle von unten nach oben. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
302 \end{enumerate} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
303 \end{block} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
304 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
305 \[ S \rightarrow AB \mid BC, \quad A \rightarrow BA \mid a, \quad B \rightarrow CC \mid b, \quad C \rightarrow AB \mid a \] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
306 \begin{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
307 \extrarowsep=5pt |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
308 \begin{tabu}to .8\textwidth{r|X[c]|X[c]|X[c]|X[c]|} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
309 \tabucline{2-2} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
310 4 & \alt<-4>{}{$S,\ldots$} \\ \tabucline{2-3} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
311 3 & \alt<-3>{}{$\emptyset$} & \alt<-3>{}{$S, A, C$} \\ \tabucline{2-4} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
312 2 & \alt<-2>{}{$A$} & \alt<-2>{}{$B$} & \alt<-2>{}{$B$} \\ \tabucline{2-5} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
313 1 & \alt<-1>{}{$B$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} \\ \tabucline{2-5} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
314 \multicolumn{1}{r}{} & \multicolumn{1}{c}{\alert{b}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
315 \end{tabu} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
316 \end{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
317 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
318 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
319 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
320 \defineUnit{pda}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
321 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
322 \frametitle{Kellerautomaten} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
323 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
324 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
325 \begin{definition}[Kellerautomat] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
326 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
327 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
328 \item endlichen Menge von \alert{Zuständen} $Q$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
329 \item endlichen \alert{Eingabealphabet} $\Sigma$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
330 \item endlichen \alert{Kelleralphabet} $\Gamma$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
331 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
332 \item \alert{Startzustand} $q_0 \in Q$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
333 \item \alert{Kellerinitialisierung} $Z_0 \in \Gamma$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
334 \item Menge von \alert{Endzuständen} $F \subseteq Q$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
335 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
336 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
337 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
338 \begin{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
339 \begin{tikzpicture}[automaton, node distance=4cm] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
340 \node[state] (q0) {$q_i$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
341 \node[state] (q1) [right of = q0] {$q_j$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
342 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
343 \draw[every edge] (q0) edge node {$a, X/\gamma$} (q1); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
344 \end{tikzpicture} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
345 \end{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
346 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
347 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
348 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
349 \defineUnit{pdaakzeptanz}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
350 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
351 \frametitle{Kellerautomaten} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
352 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
353 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
354 \begin{definition}[Kellerautomat] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
355 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
356 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
357 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
358 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
359 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
360 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
361 \vfill |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
362 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
363 \begin{definition}[Akzeptanz] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
364 Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit Endzustand} gdw |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
365 \[ \exists \alert{f \in F}, \gamma \in \Gamma^*.(q_0, w, Z_0) \rightarrow_P^* (\alert{f}, \epsilon, \gamma) \] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
366 Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit leerem Keller} gdw |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
367 \[ \exists q \in Q.(q_0, w, Z_0) \rightarrow_P^* (q, \epsilon, \alert{\epsilon}) \] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
368 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
369 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
370 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
371 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
372 \defineUnit{pdabeispiel}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
373 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
374 \frametitle{Kellerautomaten} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
375 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
376 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
377 \begin{definition}[Kellerautomat] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
378 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
379 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
380 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
381 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
382 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
383 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
384 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
385 \vfill |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
386 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
387 \begin{example}[] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
388 PDA akzeptierend \alert{mit leerem Keller} zu $L = \left\{ a^nb^n \mid n \in \N \right\}$. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
389 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
390 \centering |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
391 \begin{tikzpicture}[automaton] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
392 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
393 \node[state, initial] (q0) {$q_0$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
394 \node[state] (q1) [right of = q0] {$q_1$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
395 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
396 \draw[->] (q0) edge [bend left] node {$\epsilon, A/A$} (q1); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
397 \draw[->] (q0) edge [bend right] node [below] {$\epsilon, Z_0/Z_0$} (q1); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
398 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
399 \draw[->] (q0) edge [loop above] node {$a, Z_0/AZ_0$} (q0); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
400 \draw[->] (q0) edge [loop below] node {$a, A/AA$} (q0); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
401 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
402 \draw[->] (q1) edge [loop above] node {$b, A/\epsilon$} (q1); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
403 \draw[->] (q1) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q1); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
404 \end{tikzpicture} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
405 \end{example} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
406 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
407 } |
43
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
408 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
409 \defineUnit{kontextfreiesprachen}{% |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
410 \begin{frame} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
411 \frametitle{Kontextfreie Sprachen} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
412 \setbeamercovered{dynamic} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
413 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
414 \begin{center} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
415 \begin{tikzpicture}[node distance=3cm] |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
416 \node (CFG) {CFG}; |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
417 \node (CNF) [right of = CFG] {CNF}; |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
418 \node (PDAe) [right of = CNF] {PDA$_\epsilon$}; |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
419 \node (PDAf) [right of = PDAe] {PDA$_F$}; |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
420 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
421 \draw [every edge, <->] (CFG) -- (CNF); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
422 \draw [every edge, <->] (CNF) -- (PDAe); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
423 \draw [every edge, <->] (PDAe) -- (PDAf); |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
424 \end{tikzpicture} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
425 \end{center} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
426 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
427 \pause |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
428 \vfill |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
429 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
430 \begin{itemize} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
431 \item \alert{Abschlusseigenschaften} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
432 \end{itemize} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
433 \begin{table} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
434 \begin{tabu}to \textwidth{X[c]|ccccc} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
435 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
436 REG & ja & ja & ja & ja & ja\\ |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
437 CFL & nein & ja & nein & ja & ja |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
438 \end{tabu} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
439 \end{table} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
440 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
441 \begin{itemize} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
442 \item \alert{Entscheidbarkeit} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
443 \end{itemize} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
444 \begin{table} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
445 \begin{tabu}to \textwidth{X[c]|cccc} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
446 & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
447 DFA & $\Oh(n)$ & ja & ja & ja \\ |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
448 CFG & $\Oh(n^3)$ & ja & nein & nein |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
449 \end{tabu} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
450 \end{table} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
451 \end{frame} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
452 } |