Mercurial > 13ss.theoinf
comparison notes/tex/ue07_notes.tex @ 28:fe6b8e2da038
ue07 notes
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Mon, 10 Jun 2013 23:21:11 +0200 |
parents | |
children | 19b94914c0db |
comparison
equal
deleted
inserted
replaced
27:f7b822da4fd7 | 28:fe6b8e2da038 |
---|---|
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} |