28
|
1 \documentclass[compress, german, t]{beamer} |
|
2 |
|
3 \usepackage[ngerman,english]{babel} |
|
4 \uselanguage{German} |
|
5 \languagepath{German} |
|
6 |
|
7 \usepackage[T1]{fontenc} |
|
8 \usepackage[utf8]{inputenc} |
|
9 |
|
10 \usepackage{helvet} |
|
11 \usepackage{url} |
|
12 \usepackage{listings} |
|
13 \usepackage{xcolor} |
|
14 \usepackage{tikz} |
|
15 \usepackage{pgfplots} |
|
16 \usetikzlibrary{automata} |
|
17 \usetikzlibrary{calc} |
|
18 \usetikzlibrary{shapes.geometric} |
|
19 \usetikzlibrary{positioning} |
|
20 \usepackage{tabu} |
|
21 |
|
22 \usepackage{beamerthemeLEA2} |
|
23 |
|
24 \newcommand{\N} {\mathbb{N}} % natürliche Zahlen |
|
25 \newcommand{\Z} {\mathbb{Z}} % ganze Zahlen |
|
26 \newcommand{\R} {\mathbb{R}} % reelle Zahlen |
|
27 \newcommand{\Prob} {\mathrm{P}} % Wahrscheinlichkeit |
|
28 \newcommand{\Oh} {\mathcal{O}} % O-Notation (Landau-Symbole) |
|
29 \newcommand{\mycite}[1]{\textcolor{tumgreen}{[#1]}} |
|
30 |
|
31 \tikzstyle{every edge} = [draw,very thick,->,>=latex] |
|
32 \tikzstyle{every state} = [circle,thick,draw,fill=tumblue!10] |
|
33 \tikzstyle{automaton} = [shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] |
|
34 \tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\LARGE] |
|
35 |
|
36 \title{Übung 7: CYK und Kellerautomaten} |
|
37 \subtitle{Theoretische Informatik Sommersemester 2013} |
|
38 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} |
|
39 |
|
40 \begin{document} |
|
41 |
|
42 \begin{frame} |
|
43 \titlepage |
|
44 \end{frame} |
|
45 |
|
46 \begin{frame} |
|
47 \frametitle{CYK} |
|
48 \setbeamercovered{dynamic} |
|
49 |
|
50 \begin{definition}[Cocke-Younger-Kasami-Algorithmus] |
|
51 Der \alert{CYK-Algorithmus} entscheidet das Wortproblem für kontextfreie Grammatiken in Chomsky-Normalform in $\Oh(n^3)$. \\ |
|
52 Gegeben eine \alert{Grammatik} $G = (V, \Sigma, P, S)$ in CNF und ein \alert{Wort} $w = a_1 \ldots a_n \in \Sigma^*$. |
|
53 Mit \[ V_{ij} := \left\{ A \in V \mid A \rightarrow_G^* \alert{a_i \ldots a_j} \right\}\] |
|
54 ist \[ w \in L(G) \Leftrightarrow S \in V_{\alert{1n}} \] |
|
55 \end{definition} |
|
56 |
|
57 \begin{align*} |
|
58 V_{ii} &= \left\{ A \in V \mid (A \rightarrow a_i) \in P \right\} \\ |
|
59 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\} |
|
60 \end{align*} |
|
61 |
|
62 \end{frame} |
|
63 |
|
64 \begin{frame} |
|
65 \frametitle{CYK} |
|
66 \setbeamercovered{dynamic} |
|
67 |
|
68 \begin{block}{Idee} |
|
69 Kombiniere \alert{Teilwörter} zum ganzen Wort, wenn möglich. |
|
70 \begin{enumerate} |
|
71 \item Initialisiere mit den \alert{$V_{ii}$}. |
|
72 \item<3-5> Befülle die Tabelle von unten nach oben. |
|
73 \end{enumerate} |
|
74 \end{block} |
|
75 |
|
76 \[ S \rightarrow AB \mid BC, \quad A \rightarrow BA \mid a, \quad B \rightarrow CC \mid b, \quad C \rightarrow AB \mid a \] |
|
77 \begin{center} |
|
78 \extrarowsep=5pt |
|
79 \begin{tabu}to .8\textwidth{r|X[c]|X[c]|X[c]|X[c]|} |
|
80 \tabucline{2-2} |
|
81 4 & \alt<-4>{}{$S,\ldots$} \\ \tabucline{2-3} |
|
82 3 & \alt<-3>{}{$\emptyset$} & \alt<-3>{}{$S, A, C$} \\ \tabucline{2-4} |
|
83 2 & \alt<-2>{}{$A$} & \alt<-2>{}{$B$} & \alt<-2>{}{$B$} \\ \tabucline{2-5} |
|
84 1 & \alt<-1>{}{$B$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} \\ \tabucline{2-5} |
|
85 \multicolumn{1}{r}{} & \multicolumn{1}{c}{\alert{b}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} \\ |
|
86 \end{tabu} |
|
87 \end{center} |
|
88 \end{frame} |
|
89 |
|
90 \begin{frame} |
|
91 \frametitle{Kellerautomaten} |
|
92 \setbeamercovered{dynamic} |
|
93 |
|
94 \begin{definition}[Kellerautomat] |
|
95 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem |
|
96 \begin{itemize} |
|
97 \item endlichen Menge von \alert{Zuständen} $Q$ |
|
98 \item endlichen \alert{Eingabealphabet} $\Sigma$ |
|
99 \item endlichen \alert{Kelleralphabet} $\Gamma$ |
|
100 \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \times \Gamma \mapsto P(Q \times \Gamma^*)$ |
|
101 \item \alert{Startzustand} $q_0 \in Q$ |
|
102 \item \alert{Kellerinitialisierung} $Z_0 \in \Gamma$ |
|
103 \item Menge von \alert{Endzuständen} $F \subseteq Q$ |
|
104 \end{itemize} |
|
105 \end{definition} |
|
106 \end{frame} |
|
107 |
|
108 \begin{frame} |
|
109 \frametitle{Kellerautomaten} |
|
110 \setbeamercovered{dynamic} |
|
111 |
|
112 \begin{definition}[Kellerautomat] |
|
113 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem |
|
114 \begin{itemize} |
|
115 \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \times \Gamma \mapsto P(Q \times \Gamma^*)$ |
|
116 \end{itemize} |
|
117 \end{definition} |
|
118 |
|
119 \vfill |
|
120 |
|
121 \begin{definition}[Akzeptanz] |
|
122 Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit Endzustand} gdw |
|
123 \[ \exists \alert{f \in F}, \gamma \in \Gamma^*.(q_0, w, Z_0) \rightarrow_P^* (\alert{f}, \epsilon, \gamma) \] |
|
124 Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit leerem Keller} gdw |
|
125 \[ \exists q \in Q.(q_0, w, Z_0) \rightarrow_P^* (q, \epsilon, \alert{\epsilon}) \] |
|
126 \end{definition} |
|
127 \end{frame} |
|
128 |
|
129 \begin{frame} |
|
130 \frametitle{Kellerautomaten} |
|
131 \setbeamercovered{dynamic} |
|
132 |
|
133 \begin{definition}[Kellerautomat] |
|
134 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem |
|
135 \begin{itemize} |
|
136 \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \times \Gamma \mapsto P(Q \times \Gamma^*)$ |
|
137 \end{itemize} |
|
138 \end{definition} |
|
139 |
|
140 \vfill |
|
141 |
|
142 \begin{example}[] |
|
143 PDA akzeptierend \alert{mit leerem Keller} zu $L = \left\{ a^nb^n \mid n \in \N \right\}$. |
|
144 |
|
145 \centering |
|
146 \begin{tikzpicture}[automaton] |
|
147 |
|
148 \node[state, initial] (q0) {$q_0$}; |
|
149 \node[state] (q1) [right of = q0] {$q_1$}; |
|
150 |
|
151 \draw[->] (q0) edge [bend left] node {$\epsilon, A/A$} (q1); |
|
152 \draw[->] (q0) edge [bend right] node [below] {$\epsilon, Z_0/Z_0$} (q1); |
|
153 |
|
154 \draw[->] (q0) edge [loop above] node {$a, Z_0/AZ_0$} (q0); |
|
155 \draw[->] (q0) edge [loop below] node {$a, A/AA$} (q0); |
|
156 |
|
157 \draw[->] (q1) edge [loop above] node {$b, A/\epsilon$} (q1); |
|
158 \draw[->] (q1) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q1); |
|
159 \end{tikzpicture} |
|
160 \end{example} |
|
161 \end{frame} |
|
162 |
|
163 \begin{frame} |
|
164 \frametitle{Kontextfreie Sprachen} |
|
165 \setbeamercovered{dynamic} |
|
166 |
|
167 \begin{center} |
|
168 \begin{tikzpicture}[node distance=3cm] |
|
169 \node (CFG) {CFG}; |
|
170 \node (CNF) [right of = CFG] {CNF}; |
|
171 \node (PDAe) [right of = CNF] {PDA$_\epsilon$}; |
|
172 \node (PDAf) [right of = PDAe] {PDA$_F$}; |
|
173 |
|
174 \draw [every edge, <->] (CFG) -- (CNF); |
|
175 \draw [every edge, <->] (CNF) -- (PDAe); |
|
176 \draw [every edge, <->] (PDAe) -- (PDAf); |
|
177 \end{tikzpicture} |
|
178 \end{center} |
|
179 |
|
180 \pause |
|
181 \vfill |
|
182 |
|
183 \begin{itemize} |
|
184 \item \alert{Abschlusseigenschaften} |
|
185 \end{itemize} |
|
186 \begin{table} |
|
187 \begin{tabu}to \textwidth{X[c]|ccccc} |
|
188 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{} |
|
189 REG & ja & ja & ja & ja & ja\\ |
|
190 CFL & nein & ja & nein & ja & ja |
|
191 \end{tabu} |
|
192 \end{table} |
|
193 \begin{itemize} |
|
194 \item \alert{Entscheidbarkeit} |
|
195 \end{itemize} |
|
196 \begin{table} |
|
197 \begin{tabu}to \textwidth{X[c]|cccc} |
|
198 & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{} |
|
199 DFA & $\Oh(n)$ & ja & ja & ja \\ |
|
200 CFG & $\Oh(n^3)$ & ja & nein & nein |
|
201 \end{tabu} |
|
202 \end{table} |
|
203 \end{frame} |
|
204 |
|
205 \end{document} |