# HG changeset patch # User Markus Kaiser # Date 1400095804 -7200 # Node ID 1359f5a6aa604c0d9a6c7c074f3d2096a593a392 # Parent 0f7daeda8363b99aec8f93ca11861699ccf9f34d first half of fifth notes diff -r 0f7daeda8363 -r 1359f5a6aa60 notes/tex/grammars.tex --- a/notes/tex/grammars.tex Sun May 11 00:27:30 2014 +0200 +++ b/notes/tex/grammars.tex Wed May 14 21:30:04 2014 +0200 @@ -110,10 +110,12 @@ \setbeamercovered{dynamic} \begin{block}{Induktive Sprachdefinition} - Die \alert{induktive Definition} ($\Longrightarrow$) erzeugt Wörter \alert{bottom-up}, setzt also kleine Wörter zu größeren zusammen. + Die \alert{induktive Definition} zu einer Grammatik $G$ ergibt sich direkt aus ihren Produktionen. Dabei werden kleinere Worte zu größeren Worten \alert{zusammengesetzt}, die Definition erfolgt \structure{bottom-up}. \end{block} - \begin{example}[Vorbereitung 3] + \vfill + + \begin{example} Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$: \begin{align*} @@ -344,6 +346,34 @@ \end{frame} } +\defineUnit{ogden}{% +\begin{frame} + \frametitle{Ogden Lemma für kontextfreie Sprachen} + \setbeamercovered{dynamic} + + \begin{theorem}[Ogden Lemma für kontextfreie Sprachen] + Sei $L \subseteq \Sigma^*$ kontextfrei.\\ + Dann gibt es ein $n > 0$, so dass für \alert{jedes} $z \in L$ mit $|z| \geq n$ gilt:\\ + Für \alert{jede} Markierung $M$ von \alert{mindestens $n$} Buchstaben in $z$ gibt es eine Zerlegung $z = uvwxy$ mit + \begin{itemize} + \item $|vx|_M \alert{\geq 1}$ + \item $|vwx|_M \alert{\leq n}$ + \item $\forall i \alert{\geq 0}. uv^iwx^iy \in L$ + \end{itemize} + \end{theorem} + + \hfill + + \begin{example}[Markierung] + Sei $w = abaabaaa$ ein Wort. Dann ist + \begin{align} + w = a\structure{ba}a\structure{b}aaa + \end{align} + eine Markierung mit $|w|_M = 3$. + \end{example} +\end{frame} +} + \defineUnit{cyk}{% \begin{frame} \frametitle{CYK} @@ -392,24 +422,34 @@ \end{frame} } +\defineUnit{greibach}{% +\begin{frame} + \frametitle{Greibach Normalform} + + Stuff. +\end{frame} +} + \defineUnit{pda}{% \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 + 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 endlichen Menge von \alert{Zuständen} $Q$ - \item endlichen \alert{Eingabealphabet} $\Sigma$ - \item endlichen \alert{Kelleralphabet} $\Gamma$ - \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to 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$ + \item endlichen Menge von \structure{Zuständen} $Q$ + \item endlichen \structure{Eingabealphabet} $\Sigma$ + \item endlichen \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$ + \item \structure{Kellerinitialisierung} $Z_0 \in \Gamma$ + \item Menge von \structure{Endzuständen} $F \subseteq Q$ \end{itemize} \end{definition} + \vfill + \begin{center} \begin{tikzpicture}[automaton, node distance=4cm] \node[state] (q0) {$q_i$}; @@ -427,18 +467,18 @@ \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 + 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 \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ + \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ \end{itemize} \end{definition} \vfill \begin{definition}[Akzeptanz] - Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit Endzustand} gdw + Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \structure{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 + Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \structure{mit leerem Keller} gdw \[ \exists q \in Q.(q_0, w, Z_0) \rightarrow_P^* (q, \epsilon, \alert{\epsilon}) \] \end{definition} \end{frame} @@ -450,32 +490,34 @@ \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 + 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 \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ + \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to 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\}$. + PDA akzeptierend \alert{mit leerem Keller} zu $L = \left\{ a^nb^n \mid n \in \N_0 \right\}$. + \bigskip \centering \begin{tikzpicture}[automaton] \node[state, initial] (q0) {$q_0$}; \node[state] (q1) [right of = q0] {$q_1$}; + \node[state] (q2) [right of = q1] {$q_2$}; - \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 {$\epsilon, Z_0/\epsilon$}; - \draw[->] (q0) edge [loop above] node {$a, Z_0/AZ_0$} (q0); - \draw[->] (q0) edge [loop below] node {$a, A/AA$} (q0); + \draw[->] (q0) edge node {$a, Z_0/AZ_0$} (q1); + \draw[->] (q1) edge node {$\epsilon, A/A$} (q2); - \draw[->] (q1) edge [loop above] node {$b, A/\epsilon$} (q1); - \draw[->] (q1) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q1); + \draw[->] (q1) edge [loop above] node {$a, */A*$} (q1); + + \draw[->] (q2) edge [loop above] node {$b, */\epsilon$} (q2); \end{tikzpicture} \end{example} \end{frame} diff -r 0f7daeda8363 -r 1359f5a6aa60 notes/tex/ue05_notes.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/ue05_notes.tex Wed May 14 21:30:04 2014 +0200 @@ -0,0 +1,16 @@ +\input{preamble.tex} +\input{frames.tex} + +\title{Übung 5: Ogden-Lemma und Kellerautomaten} +\subtitle{Theoretische Informatik Sommersemester 2014} +\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} + +\begin{document} +\showUnit{titel} +\showUnit{induktivesprachdefinition} +\showUnit{ogden} +\showUnit{greibach} +\showUnit{pda} +\showUnit{pdaakzeptanz} +\showUnit{pdabeispiel} +\end{document}