Mercurial > 13ss.theoinf

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

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
transition notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Thu, 11 Jul 2013 22:06:26 +0200
parents 27fedbbdab6d
children 72ac27051d7e
comparison
equal deleted inserted replaced
43:c14b92bfa07f 44:15351d87ce76
1 \input{preamble.tex} 1 \input{preamble.tex}
2 \input{frames.tex}
2 3
3 \title{Übung 7: CYK und Kellerautomaten} 4 \title{Übung 7: CYK und Kellerautomaten}
4 \subtitle{Theoretische Informatik Sommersemester 2013} 5 \subtitle{Theoretische Informatik Sommersemester 2013}
5 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} 6 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
6 7
7 \begin{document} 8 \begin{document}
8 9 \showUnit{titel}
9 \begin{frame} 10 \showUnit{cyk}
10 \titlepage 11 \showUnit{cykbeispiel}
11 \end{frame} 12 \showUnit{pda}
12 13 \showUnit{pdaakzeptanz}
13 \begin{frame} 14 \showUnit{pdabeispiel}
14 \frametitle{CYK}
15 \setbeamercovered{dynamic}
16
17 \begin{definition}[Cocke-Younger-Kasami-Algorithmus]
18 Der \alert{CYK-Algorithmus} entscheidet das Wortproblem für kontextfreie Grammatiken in Chomsky-Normalform in $\Oh(n^3)$. \\
19 Gegeben eine \alert{Grammatik} $G = (V, \Sigma, P, S)$ in CNF und ein \alert{Wort} $w = a_1 \ldots a_n \in \Sigma^*$.
20 Mit \[ V_{ij} := \left\{ A \in V \mid A \rightarrow_G^* \alert{a_i \ldots a_j} \right\}\]
21 ist \[ w \in L(G) \Leftrightarrow S \in V_{\alert{1n}} \]
22 \end{definition}
23
24 \begin{align*}
25 V_{ii} &= \left\{ A \in V \mid (A \rightarrow a_i) \in P \right\} \\
26 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\}
27 \end{align*}
28
29 \end{frame}
30
31 \begin{frame}
32 \frametitle{CYK}
33 \setbeamercovered{dynamic}
34
35 \begin{block}{Idee}
36 Kombiniere \alert{Teilwörter} zum ganzen Wort, wenn möglich.
37 \begin{enumerate}
38 \item Initialisiere mit den \alert{$V_{ii}$}.
39 \item<3-5> Befülle die Tabelle von unten nach oben.
40 \end{enumerate}
41 \end{block}
42
43 \[ S \rightarrow AB \mid BC, \quad A \rightarrow BA \mid a, \quad B \rightarrow CC \mid b, \quad C \rightarrow AB \mid a \]
44 \begin{center}
45 \extrarowsep=5pt
46 \begin{tabu}to .8\textwidth{r|X[c]|X[c]|X[c]|X[c]|}
47 \tabucline{2-2}
48 4 & \alt<-4>{}{$S,\ldots$} \\ \tabucline{2-3}
49 3 & \alt<-3>{}{$\emptyset$} & \alt<-3>{}{$S, A, C$} \\ \tabucline{2-4}
50 2 & \alt<-2>{}{$A$} & \alt<-2>{}{$B$} & \alt<-2>{}{$B$} \\ \tabucline{2-5}
51 1 & \alt<-1>{}{$B$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} \\ \tabucline{2-5}
52 \multicolumn{1}{r}{} & \multicolumn{1}{c}{\alert{b}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} \\
53 \end{tabu}
54 \end{center}
55 \end{frame}
56
57 \begin{frame}
58 \frametitle{Kellerautomaten}
59 \setbeamercovered{dynamic}
60
61 \begin{definition}[Kellerautomat]
62 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem
63 \begin{itemize}
64 \item endlichen Menge von \alert{Zuständen} $Q$
65 \item endlichen \alert{Eingabealphabet} $\Sigma$
66 \item endlichen \alert{Kelleralphabet} $\Gamma$
67 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$
68 \item \alert{Startzustand} $q_0 \in Q$
69 \item \alert{Kellerinitialisierung} $Z_0 \in \Gamma$
70 \item Menge von \alert{Endzuständen} $F \subseteq Q$
71 \end{itemize}
72 \end{definition}
73
74 \begin{center}
75 \begin{tikzpicture}[automaton, node distance=4cm]
76 \node[state] (q0) {$q_i$};
77 \node[state] (q1) [right of = q0] {$q_j$};
78
79 \draw[every edge] (q0) edge node {$a, X/\gamma$} (q1);
80 \end{tikzpicture}
81 \end{center}
82 \end{frame}
83
84 \begin{frame}
85 \frametitle{Kellerautomaten}
86 \setbeamercovered{dynamic}
87
88 \begin{definition}[Kellerautomat]
89 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem
90 \begin{itemize}
91 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$
92 \end{itemize}
93 \end{definition}
94
95 \vfill
96
97 \begin{definition}[Akzeptanz]
98 Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit Endzustand} gdw
99 \[ \exists \alert{f \in F}, \gamma \in \Gamma^*.(q_0, w, Z_0) \rightarrow_P^* (\alert{f}, \epsilon, \gamma) \]
100 Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit leerem Keller} gdw
101 \[ \exists q \in Q.(q_0, w, Z_0) \rightarrow_P^* (q, \epsilon, \alert{\epsilon}) \]
102 \end{definition}
103 \end{frame}
104
105 \begin{frame}
106 \frametitle{Kellerautomaten}
107 \setbeamercovered{dynamic}
108
109 \begin{definition}[Kellerautomat]
110 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem
111 \begin{itemize}
112
113 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$
114 \end{itemize}
115 \end{definition}
116
117 \vfill
118
119 \begin{example}[]
120 PDA akzeptierend \alert{mit leerem Keller} zu $L = \left\{ a^nb^n \mid n \in \N \right\}$.
121
122 \centering
123 \begin{tikzpicture}[automaton]
124
125 \node[state, initial] (q0) {$q_0$};
126 \node[state] (q1) [right of = q0] {$q_1$};
127
128 \draw[->] (q0) edge [bend left] node {$\epsilon, A/A$} (q1);
129 \draw[->] (q0) edge [bend right] node [below] {$\epsilon, Z_0/Z_0$} (q1);
130
131 \draw[->] (q0) edge [loop above] node {$a, Z_0/AZ_0$} (q0);
132 \draw[->] (q0) edge [loop below] node {$a, A/AA$} (q0);
133
134 \draw[->] (q1) edge [loop above] node {$b, A/\epsilon$} (q1);
135 \draw[->] (q1) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q1);
136 \end{tikzpicture}
137 \end{example}
138 \end{frame}
139
140 \begin{frame}
141 \frametitle{Kontextfreie Sprachen}
142 \setbeamercovered{dynamic}
143
144 \begin{center}
145 \begin{tikzpicture}[node distance=3cm]
146 \node (CFG) {CFG};
147 \node (CNF) [right of = CFG] {CNF};
148 \node (PDAe) [right of = CNF] {PDA$_\epsilon$};
149 \node (PDAf) [right of = PDAe] {PDA$_F$};
150
151 \draw [every edge, <->] (CFG) -- (CNF);
152 \draw [every edge, <->] (CNF) -- (PDAe);
153 \draw [every edge, <->] (PDAe) -- (PDAf);
154 \end{tikzpicture}
155 \end{center}
156
157 \pause
158 \vfill
159
160 \begin{itemize}
161 \item \alert{Abschlusseigenschaften}
162 \end{itemize}
163 \begin{table}
164 \begin{tabu}to \textwidth{X[c]|ccccc}
165 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{}
166 REG & ja & ja & ja & ja & ja\\
167 CFL & nein & ja & nein & ja & ja
168 \end{tabu}
169 \end{table}
170
171 \begin{itemize}
172 \item \alert{Entscheidbarkeit}
173 \end{itemize}
174 \begin{table}
175 \begin{tabu}to \textwidth{X[c]|cccc}
176 & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{}
177 DFA & $\Oh(n)$ & ja & ja & ja \\
178 CFG & $\Oh(n^3)$ & ja & nein & nein
179 \end{tabu}
180 \end{table}
181 \end{frame}
182
183 \end{document} 15 \end{document}