# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1401575392 -7200
# Node ID 44fd483bde00313ec9ce2c61ac349c0f33b5765b
# Parent  322b0166cc246c911f18a7958657a2547c02a0a6
week seven sheet and notes

diff -r 322b0166cc24 -r 44fd483bde00 notes/complete_notes.pdf
Binary file notes/complete_notes.pdf has changed
diff -r 322b0166cc24 -r 44fd483bde00 notes/tex/complete_notes.tex
--- a/notes/tex/complete_notes.tex	Thu May 22 12:41:35 2014 +0200
+++ b/notes/tex/complete_notes.tex	Sun Jun 01 00:29:52 2014 +0200
@@ -50,4 +50,11 @@
 \showUnit{pda}
 \showUnit{pdaakzeptanz}
 \showUnit{pdabeispiel}
+
+%ue06
+% nothing here
+
+%ue07
+\showUnit{dpda}
+\showUnit{lrgrammars}
 \end{document}
diff -r 322b0166cc24 -r 44fd483bde00 notes/tex/grammars.tex
--- a/notes/tex/grammars.tex	Thu May 22 12:41:35 2014 +0200
+++ b/notes/tex/grammars.tex	Sun Jun 01 00:29:52 2014 +0200
@@ -656,6 +656,104 @@
 \end{frame}
 }
 
+\defineUnit{dpda}{%
+\begin{frame}
+    \frametitle{Kellerautomaten}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[Kellerautomat]
+        Ein \structure{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem
+        \begin{itemize}
+            \item \structure{Zustandsmenge} $Q$, \structure{Eingabealphabet} $\Sigma$, \structure{Kelleralphabet} $\Gamma$
+            \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$
+            \item \structure{Startzustand} $q_0 \in Q$, \structure{Kellerinitialisierung} $Z_0 \in \Gamma$
+            \item Menge von \structure{Endzuständen} $F \subseteq Q$
+        \end{itemize}
+    \end{definition}
+
+    \vfill
+
+    \begin{definition}[Deterministischer Kellerautomat]
+        Ein PDA heißt \structure{deterministisch (DPDA)} wenn \alert{für alle} Zustände $q \in Q$, Buchstaben $a \in \Sigma$ und Kellerbuchstaben $X \in \Gamma$ gilt
+        \begin{align}
+            \abs{\delta(q, a, Z)} + \abs{\delta(q, \epsilon, Z)} \leq 1
+        \end{align}
+    \end{definition}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Präfixbedingung}
+
+    \begin{definition}[Präfixbedingung]
+        Eine Sprache $L$ erfüllt die \structure{Präfixbedingung}, wenn kein Wort der Sprache echtes Präfix eines anderen Wortes der Sprache ist.\\
+        \begin{align}
+            \forall w \in L\ \alert{\forall s \in \Sigma^+}.\ ws \alert{\not\in} L
+        \end{align}
+    \end{definition}
+
+    \vfill
+
+    \begin{theorem}[]
+        \structure{Deterministisch kontextfreie Sprachen} werden genau dann von einem \structure{DPDA mit leerem Keller} akzeptiert, wenn sie die \alert{Präfixbedingung erfüllen}.
+    \end{theorem}
+\end{frame}
+}
+
+\defineUnit{lrgrammars}{%
+\begin{frame}
+    \frametitle{Parsing}
+
+    \begin{definition}[Parsing]
+        Beim \structure{Parsing} wird einem Wort ein Ableitungsbaum in einer Grammatik zugeordnet, indem \structure{bottom-up} die Produktionen (\structure{Reduktionen}) \alert{rückwärts} angewandt werden.\\
+        Es wird immer die linkestmögliche Reduktion angewandt.
+    \end{definition}
+    \begin{definition}[Lookahead]
+        Ein \structure{Lookahead} der Länge $k$ legt fest, dass eine Reduktion nur dann angewandt werden darf, wenn die folgenden $k$ Zeichen im Wort mit dem Lookahead übereinstimmen.
+    \end{definition}
+
+    \vfill
+
+    \begin{example}
+        \begin{columns}[T]
+            \begin{column}{.4\textwidth}
+                \vspace{-1em}
+                \begin{align}
+                    S &\to Ac \mid Bbc\\
+                    A &\to ab\\
+                    B &\to a
+                \end{align}
+            \end{column}
+            \begin{column}{.4\textwidth}
+                \begin{tabu}to \textwidth{X|X}
+                    Produktion & Lookahead \\ \tabucline{}
+                    $A \to ab$ & $c$ \\
+                    $B \to a$ & $d$
+                \end{tabu}
+            \end{column}
+        \end{columns}
+        \vspace{.5em}
+        Gegeben das Wort \structure{abc}.\\
+        Dann darf \alert{$B \to A$} nicht angewandt werden, \alert{$A \to ab$} jedoch schon.
+    \end{example}
+\end{frame}
+
+\begin{frame}[c]
+    \frametitle{LR($k$)-Grammatik}
+    \begin{definition}[LR($k$)-Grammatik]
+        Eine CFG ist eine \structure{LR($k$)-Grammatik}, wenn Lookaheads der Länge $k$ genügen, um jedem Wort eine eindeutige Ableitung zuzuordnen.
+    \end{definition}
+
+    \vspace{2em}
+
+    \begin{theorem}[]
+        Die LR($0$)-Grammatiken sind eine \structure{echte Teilmenge} der LR($1$)-Grammatiken. Diese entspechen genau den \structure{deterministisch kontextfreien Sprachen}.
+        \begin{align}
+            LR(0) \subset LR(1) = LR(k \geq 1) = DCFL
+        \end{align}
+    \end{theorem}
+\end{frame}
+}
+
 \defineUnit{kontextfreiesprachen}{%
 \begin{frame}
     \frametitle{Kontextfreie Sprachen}
diff -r 322b0166cc24 -r 44fd483bde00 notes/tex/ue07_notes.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue07_notes.tex	Sun Jun 01 00:29:52 2014 +0200
@@ -0,0 +1,12 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 6: DPDAs und LR-Grammatiken}
+\subtitle{Theoretische Informatik Sommersemester 2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{dpda}
+\showUnit{lrgrammars}
+\end{document}
diff -r 322b0166cc24 -r 44fd483bde00 notes/ue07_notes.pdf
Binary file notes/ue07_notes.pdf has changed
diff -r 322b0166cc24 -r 44fd483bde00 ue07.pdf
Binary file ue07.pdf has changed