Mercurial > 13ss.theoinf
annotate notes/tex/ue07_notes.tex @ 30:4e28756e3dba
allow epsilon-edges in PDAs
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Mon, 10 Jun 2013 23:54:54 +0200 |
| parents | 19b94914c0db |
| children | 90ffda7e20c7 |
| rev | line source |
|---|---|
| 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$ | |
|
30
4e28756e3dba
allow epsilon-edges in PDAs
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
29
diff
changeset
|
100 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \mapsto P(Q \times \Gamma^*)$ |
| 28 | 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} | |
|
29
19b94914c0db
add small example to pda definition
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
28
diff
changeset
|
106 |
|
19b94914c0db
add small example to pda definition
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
28
diff
changeset
|
107 \begin{center} |
|
19b94914c0db
add small example to pda definition
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
28
diff
changeset
|
108 \begin{tikzpicture}[automaton, node distance=4cm] |
|
19b94914c0db
add small example to pda definition
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
28
diff
changeset
|
109 \node[state] (q0) {$q_i$}; |
|
19b94914c0db
add small example to pda definition
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
28
diff
changeset
|
110 \node[state] (q1) [right of = q0] {$q_j$}; |
|
19b94914c0db
add small example to pda definition
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
28
diff
changeset
|
111 |
|
19b94914c0db
add small example to pda definition
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
28
diff
changeset
|
112 \draw[every edge] (q0) edge node {$a, X/\gamma$} (q1); |
|
19b94914c0db
add small example to pda definition
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
28
diff
changeset
|
113 \end{tikzpicture} |
|
19b94914c0db
add small example to pda definition
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
28
diff
changeset
|
114 \end{center} |
| 28 | 115 \end{frame} |
| 116 | |
| 117 \begin{frame} | |
| 118 \frametitle{Kellerautomaten} | |
| 119 \setbeamercovered{dynamic} | |
| 120 | |
| 121 \begin{definition}[Kellerautomat] | |
| 122 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem | |
| 123 \begin{itemize} | |
|
30
4e28756e3dba
allow epsilon-edges in PDAs
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
29
diff
changeset
|
124 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \mapsto P(Q \times \Gamma^*)$ |
| 28 | 125 \end{itemize} |
| 126 \end{definition} | |
| 127 | |
| 128 \vfill | |
| 129 | |
| 130 \begin{definition}[Akzeptanz] | |
| 131 Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit Endzustand} gdw | |
| 132 \[ \exists \alert{f \in F}, \gamma \in \Gamma^*.(q_0, w, Z_0) \rightarrow_P^* (\alert{f}, \epsilon, \gamma) \] | |
| 133 Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit leerem Keller} gdw | |
| 134 \[ \exists q \in Q.(q_0, w, Z_0) \rightarrow_P^* (q, \epsilon, \alert{\epsilon}) \] | |
| 135 \end{definition} | |
| 136 \end{frame} | |
| 137 | |
| 138 \begin{frame} | |
| 139 \frametitle{Kellerautomaten} | |
| 140 \setbeamercovered{dynamic} | |
| 141 | |
| 142 \begin{definition}[Kellerautomat] | |
| 143 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem | |
| 144 \begin{itemize} | |
|
30
4e28756e3dba
allow epsilon-edges in PDAs
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
29
diff
changeset
|
145 |
|
4e28756e3dba
allow epsilon-edges in PDAs
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
29
diff
changeset
|
146 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \mapsto P(Q \times \Gamma^*)$ |
| 28 | 147 \end{itemize} |
| 148 \end{definition} | |
| 149 | |
| 150 \vfill | |
| 151 | |
| 152 \begin{example}[] | |
| 153 PDA akzeptierend \alert{mit leerem Keller} zu $L = \left\{ a^nb^n \mid n \in \N \right\}$. | |
| 154 | |
| 155 \centering | |
| 156 \begin{tikzpicture}[automaton] | |
| 157 | |
| 158 \node[state, initial] (q0) {$q_0$}; | |
| 159 \node[state] (q1) [right of = q0] {$q_1$}; | |
| 160 | |
| 161 \draw[->] (q0) edge [bend left] node {$\epsilon, A/A$} (q1); | |
| 162 \draw[->] (q0) edge [bend right] node [below] {$\epsilon, Z_0/Z_0$} (q1); | |
| 163 | |
| 164 \draw[->] (q0) edge [loop above] node {$a, Z_0/AZ_0$} (q0); | |
| 165 \draw[->] (q0) edge [loop below] node {$a, A/AA$} (q0); | |
| 166 | |
| 167 \draw[->] (q1) edge [loop above] node {$b, A/\epsilon$} (q1); | |
| 168 \draw[->] (q1) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q1); | |
| 169 \end{tikzpicture} | |
| 170 \end{example} | |
| 171 \end{frame} | |
| 172 | |
| 173 \begin{frame} | |
| 174 \frametitle{Kontextfreie Sprachen} | |
| 175 \setbeamercovered{dynamic} | |
| 176 | |
| 177 \begin{center} | |
| 178 \begin{tikzpicture}[node distance=3cm] | |
| 179 \node (CFG) {CFG}; | |
| 180 \node (CNF) [right of = CFG] {CNF}; | |
| 181 \node (PDAe) [right of = CNF] {PDA$_\epsilon$}; | |
| 182 \node (PDAf) [right of = PDAe] {PDA$_F$}; | |
| 183 | |
| 184 \draw [every edge, <->] (CFG) -- (CNF); | |
| 185 \draw [every edge, <->] (CNF) -- (PDAe); | |
| 186 \draw [every edge, <->] (PDAe) -- (PDAf); | |
| 187 \end{tikzpicture} | |
| 188 \end{center} | |
| 189 | |
| 190 \pause | |
| 191 \vfill | |
| 192 | |
| 193 \begin{itemize} | |
| 194 \item \alert{Abschlusseigenschaften} | |
| 195 \end{itemize} | |
| 196 \begin{table} | |
| 197 \begin{tabu}to \textwidth{X[c]|ccccc} | |
| 198 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{} | |
| 199 REG & ja & ja & ja & ja & ja\\ | |
| 200 CFL & nein & ja & nein & ja & ja | |
| 201 \end{tabu} | |
| 202 \end{table} | |
|
29
19b94914c0db
add small example to pda definition
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
28
diff
changeset
|
203 |
| 28 | 204 \begin{itemize} |
| 205 \item \alert{Entscheidbarkeit} | |
| 206 \end{itemize} | |
| 207 \begin{table} | |
| 208 \begin{tabu}to \textwidth{X[c]|cccc} | |
| 209 & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{} | |
| 210 DFA & $\Oh(n)$ & ja & ja & ja \\ | |
| 211 CFG & $\Oh(n^3)$ & ja & nein & nein | |
| 212 \end{tabu} | |
| 213 \end{table} | |
| 214 \end{frame} | |
| 215 | |
| 216 \end{document} |