Mercurial > 13ss.theoinf

annotate notes/tex/grammars.tex @ 58:aac2480571b8 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
rewrite ambiguous slide
author Markus Kaiser <markus.kaiser@in.tum.de>
date Tue, 30 Jul 2013 14:32:43 +0200
parents 72ac27051d7e
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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 \\
58
aac2480571b8 rewrite ambiguous slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 49
diff changeset
139 \intertext{wird zu:}
aac2480571b8 rewrite ambiguous slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 49
diff changeset
140 S &\rightarrow \alert{Ab \mid b} \\
aac2480571b8 rewrite ambiguous slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 49
diff changeset
141 A &\rightarrow \alert{aAA \mid aA \mid a}
41
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 \\
58
aac2480571b8 rewrite ambiguous slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 49
diff changeset
149 \intertext{wird zu:}
41
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 \\
58
aac2480571b8 rewrite ambiguous slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 49
diff changeset
159 \intertext{wird zu:}
41
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 \\
58
aac2480571b8 rewrite ambiguous slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 49
diff changeset
169 \intertext{wird zu:}
41
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 \vfill
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
428
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
429 \begin{itemize}
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
430 \item \alert{Abschlusseigenschaften}
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
431 \end{itemize}
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
432 \begin{table}
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
433 \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
434 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{}
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
435 REG & ja & ja & ja & ja & ja\\
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
436 CFL & nein & ja & nein & ja & ja
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
437 \end{tabu}
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
438 \end{table}
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
439
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
440 \begin{itemize}
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
441 \item \alert{Entscheidbarkeit}
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
442 \end{itemize}
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
443 \begin{table}
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
444 \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
445 & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{}
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
446 DFA & $\Oh(n)$ & ja & ja & ja \\
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
447 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
448 \end{tabu}
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
449 \end{table}
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
450 \end{frame}
c14b92bfa07f add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 41
diff changeset
451 }