14ss.theoinf: notes/tex/grammars.tex comparison

comparison notes/tex/grammars.tex @ 25:44fd483bde00

week seven sheet and notes

author	Markus Kaiser <markus.kaiser@in.tum.de>
date	Sun, 01 Jun 2014 00:29:52 +0200
parents	322b0166cc24
children	f7bcd68a0c12

comparison

equal deleted inserted replaced

-:322b0166cc24
+:44fd483bde00
 \end{tikzpicture}
 \end{example}
 \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}
 \setbeamercovered{dynamic}

Mercurial > 14ss.theoinf

comparison notes/tex/grammars.tex @ 25:44fd483bde00