# HG changeset patch # User Markus Kaiser # Date 1370899271 -7200 # Node ID fe6b8e2da038061e30efc974c857d11e79f14f5a # Parent f7b822da4fd7a93cd6b379fae235c58c6433ab63 ue07 notes diff -r f7b822da4fd7 -r fe6b8e2da038 notes/tex/ue04_notes.tex --- a/notes/tex/ue04_notes.tex Mon Jun 10 20:06:43 2013 +0200 +++ b/notes/tex/ue04_notes.tex Mon Jun 10 23:21:11 2013 +0200 @@ -148,7 +148,7 @@ \draw<-5>[->] (q1) edge node {$a,b$} (q3); \draw<-5>[->] (q2) edge node {$a,b$} (q3); \draw[->] (q3) edge [loop right] node [above] {$a,b$} (q3); - + \draw<6>[->] (q12) edge node {$a,b$} (q3); \draw<6>[->] (q0) edge node {$a,b$} (q12); \end{tikzpicture} diff -r f7b822da4fd7 -r fe6b8e2da038 notes/tex/ue07_notes.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/ue07_notes.tex Mon Jun 10 23:21:11 2013 +0200 @@ -0,0 +1,205 @@ +\documentclass[compress, german, t]{beamer} + +\usepackage[ngerman,english]{babel} +\uselanguage{German} +\languagepath{German} + +\usepackage[T1]{fontenc} +\usepackage[utf8]{inputenc} + +\usepackage{helvet} +\usepackage{url} +\usepackage{listings} +\usepackage{xcolor} +\usepackage{tikz} +\usepackage{pgfplots} +\usetikzlibrary{automata} +\usetikzlibrary{calc} +\usetikzlibrary{shapes.geometric} +\usetikzlibrary{positioning} +\usepackage{tabu} + +\usepackage{beamerthemeLEA2} + +\newcommand{\N} {\mathbb{N}} % natürliche Zahlen +\newcommand{\Z} {\mathbb{Z}} % ganze Zahlen +\newcommand{\R} {\mathbb{R}} % reelle Zahlen +\newcommand{\Prob} {\mathrm{P}} % Wahrscheinlichkeit +\newcommand{\Oh} {\mathcal{O}} % O-Notation (Landau-Symbole) +\newcommand{\mycite}[1]{\textcolor{tumgreen}{[#1]}} + +\tikzstyle{every edge} = [draw,very thick,->,>=latex] +\tikzstyle{every state} = [circle,thick,draw,fill=tumblue!10] +\tikzstyle{automaton} = [shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] +\tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\LARGE] + +\title{Übung 7: CYK und Kellerautomaten} +\subtitle{Theoretische Informatik Sommersemester 2013} +\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} + +\begin{document} + +\begin{frame} + \titlepage +\end{frame} + +\begin{frame} + \frametitle{CYK} + \setbeamercovered{dynamic} + + \begin{definition}[Cocke-Younger-Kasami-Algorithmus] + Der \alert{CYK-Algorithmus} entscheidet das Wortproblem für kontextfreie Grammatiken in Chomsky-Normalform in $\Oh(n^3)$. \\ + Gegeben eine \alert{Grammatik} $G = (V, \Sigma, P, S)$ in CNF und ein \alert{Wort} $w = a_1 \ldots a_n \in \Sigma^*$. + Mit \[ V_{ij} := \left\{ A \in V \mid A \rightarrow_G^* \alert{a_i \ldots a_j} \right\}\] + ist \[ w \in L(G) \Leftrightarrow S \in V_{\alert{1n}} \] + \end{definition} + + \begin{align*} + V_{ii} &= \left\{ A \in V \mid (A \rightarrow a_i) \in P \right\} \\ + 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\} + \end{align*} + +\end{frame} + +\begin{frame} + \frametitle{CYK} + \setbeamercovered{dynamic} + + \begin{block}{Idee} + Kombiniere \alert{Teilwörter} zum ganzen Wort, wenn möglich. + \begin{enumerate} + \item Initialisiere mit den \alert{$V_{ii}$}. + \item<3-5> Befülle die Tabelle von unten nach oben. + \end{enumerate} + \end{block} + + \[ S \rightarrow AB \mid BC, \quad A \rightarrow BA \mid a, \quad B \rightarrow CC \mid b, \quad C \rightarrow AB \mid a \] + \begin{center} + \extrarowsep=5pt + \begin{tabu}to .8\textwidth{r|X[c]|X[c]|X[c]|X[c]|} + \tabucline{2-2} + 4 & \alt<-4>{}{$S,\ldots$} \\ \tabucline{2-3} + 3 & \alt<-3>{}{$\emptyset$} & \alt<-3>{}{$S, A, C$} \\ \tabucline{2-4} + 2 & \alt<-2>{}{$A$} & \alt<-2>{}{$B$} & \alt<-2>{}{$B$} \\ \tabucline{2-5} + 1 & \alt<-1>{}{$B$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} \\ \tabucline{2-5} + \multicolumn{1}{r}{} & \multicolumn{1}{c}{\alert{b}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} \\ + \end{tabu} + \end{center} +\end{frame} + +\begin{frame} + \frametitle{Kellerautomaten} + \setbeamercovered{dynamic} + + \begin{definition}[Kellerautomat] + Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem + \begin{itemize} + \item endlichen Menge von \alert{Zuständen} $Q$ + \item endlichen \alert{Eingabealphabet} $\Sigma$ + \item endlichen \alert{Kelleralphabet} $\Gamma$ + \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \times \Gamma \mapsto P(Q \times \Gamma^*)$ + \item \alert{Startzustand} $q_0 \in Q$ + \item \alert{Kellerinitialisierung} $Z_0 \in \Gamma$ + \item Menge von \alert{Endzuständen} $F \subseteq Q$ + \end{itemize} + \end{definition} +\end{frame} + +\begin{frame} + \frametitle{Kellerautomaten} + \setbeamercovered{dynamic} + + \begin{definition}[Kellerautomat] + Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem + \begin{itemize} + \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \times \Gamma \mapsto P(Q \times \Gamma^*)$ + \end{itemize} + \end{definition} + + \vfill + + \begin{definition}[Akzeptanz] + Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit Endzustand} gdw + \[ \exists \alert{f \in F}, \gamma \in \Gamma^*.(q_0, w, Z_0) \rightarrow_P^* (\alert{f}, \epsilon, \gamma) \] + Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit leerem Keller} gdw + \[ \exists q \in Q.(q_0, w, Z_0) \rightarrow_P^* (q, \epsilon, \alert{\epsilon}) \] + \end{definition} +\end{frame} + +\begin{frame} + \frametitle{Kellerautomaten} + \setbeamercovered{dynamic} + + \begin{definition}[Kellerautomat] + Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem + \begin{itemize} + \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \times \Gamma \mapsto P(Q \times \Gamma^*)$ + \end{itemize} + \end{definition} + + \vfill + + \begin{example}[] + PDA akzeptierend \alert{mit leerem Keller} zu $L = \left\{ a^nb^n \mid n \in \N \right\}$. + + \centering + \begin{tikzpicture}[automaton] + + \node[state, initial] (q0) {$q_0$}; + \node[state] (q1) [right of = q0] {$q_1$}; + + \draw[->] (q0) edge [bend left] node {$\epsilon, A/A$} (q1); + \draw[->] (q0) edge [bend right] node [below] {$\epsilon, Z_0/Z_0$} (q1); + + \draw[->] (q0) edge [loop above] node {$a, Z_0/AZ_0$} (q0); + \draw[->] (q0) edge [loop below] node {$a, A/AA$} (q0); + + \draw[->] (q1) edge [loop above] node {$b, A/\epsilon$} (q1); + \draw[->] (q1) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q1); + \end{tikzpicture} + \end{example} +\end{frame} + +\begin{frame} + \frametitle{Kontextfreie Sprachen} + \setbeamercovered{dynamic} + + \begin{center} + \begin{tikzpicture}[node distance=3cm] + \node (CFG) {CFG}; + \node (CNF) [right of = CFG] {CNF}; + \node (PDAe) [right of = CNF] {PDA$_\epsilon$}; + \node (PDAf) [right of = PDAe] {PDA$_F$}; + + \draw [every edge, <->] (CFG) -- (CNF); + \draw [every edge, <->] (CNF) -- (PDAe); + \draw [every edge, <->] (PDAe) -- (PDAf); + \end{tikzpicture} + \end{center} + + \pause + \vfill + + \begin{itemize} + \item \alert{Abschlusseigenschaften} + \end{itemize} + \begin{table} + \begin{tabu}to \textwidth{X[c]|ccccc} + & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{} + REG & ja & ja & ja & ja & ja\\ + CFL & nein & ja & nein & ja & ja + \end{tabu} + \end{table} + \begin{itemize} + \item \alert{Entscheidbarkeit} + \end{itemize} + \begin{table} + \begin{tabu}to \textwidth{X[c]|cccc} + & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{} + DFA & $\Oh(n)$ & ja & ja & ja \\ + CFG & $\Oh(n^3)$ & ja & nein & nein + \end{tabu} + \end{table} +\end{frame} + +\end{document} diff -r f7b822da4fd7 -r fe6b8e2da038 notes/ue07_notes.pdf Binary file notes/ue07_notes.pdf has changed