Mercurial > 13ss.theoinf
changeset 43:c14b92bfa07f
add missing slides; correct some errors
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Thu, 11 Jul 2013 21:57:50 +0200 |
| parents | 35e8bb96da7b |
| children | 15351d87ce76 |
| files | notes/tex/automatons.tex notes/tex/computation.tex notes/tex/grammars.tex |
| diffstat | 3 files changed, 281 insertions(+), 7 deletions(-) [+] |
line wrap: on
line diff
--- a/notes/tex/automatons.tex Thu Jul 11 21:25:21 2013 +0200 +++ b/notes/tex/automatons.tex Thu Jul 11 21:57:50 2013 +0200 @@ -170,7 +170,7 @@ \end{frame} } -\defineUnit{rezunfa}{% +\defineUnit{rezuenfa}{% \begin{frame} \frametitle{RE $\rightarrow$ $\epsilon$-NFA} \setbeamercovered{dynamic} @@ -365,17 +365,18 @@ \defineUnit{produktautomat}{% \begin{frame} - \frametitle{produktautomat} + \frametitle{Produktautomat} \setbeamercovered{dynamic} + \begin{theorem} - sind $m_1 = (q_1, \sigma, \delta_1, s_1, f_1)$ und $m_2 = (q_2, \sigma, \delta_2, s_2, f_2)$ dfas, dann ist der \alert{produkt-automat} + Sind $M_1 = (Q_1, \Sigma, \delta_1, s_1, F_1)$ und $M_2 = (Q_2, \Sigma, \delta_2, s_2, F_2)$ DFAs, dann ist der \alert{Produkt-Automat} \begin{align*} - m &:= (\alert{q_1 \times q_2}, \sigma, \delta, (s_1, s_2), f_1 \times f_2) \\ + M &:= (\alert{Q_1 \times Q_2}, \Sigma, \delta, (s_1, s_2), F_1 \times F_2) \\ \delta\left( (q_1, q_2), a \right) &:= \left( \alert{\delta_1}(q_1, a), \alert{\delta_2}(q_2, a) \right) \end{align*} - ein dfa, der $l(m_1) \cap l(m_2)$ akzeptiert. + ein DFA, der $L(M_1) \cap L(M_2)$ akzeptiert. \end{theorem} \end{frame} } @@ -526,7 +527,7 @@ \end{frame} } -\defineUnit{aequivalenteZustaende}{% +\defineUnit{aequivalentezustaende}{% \begin{frame} \frametitle{Äquivalenzen} \setbeamercovered{dynamic} @@ -552,7 +553,7 @@ \end{frame} } -\defineUnit{unterscheidbareZustaende}{% +\defineUnit{unterscheidbarezustaende}{% \begin{frame} \frametitle{Unterscheidbare Zustände} \setbeamercovered{dynamic} @@ -593,3 +594,90 @@ \end{tikzpicture} \end{frame} } + +\defineUnit{quotientenautomat}{% +\begin{frame}[t] + \frametitle{DFA minimieren} + \setbeamercovered{dynamic} + + \begin{block}{Idee} + Erzeuge den \alert{Quotientenautomaten}. + \begin{enumerate} + \item Entferne alle von $q_0$ \alert{nicht erreichbaren} Zustände + \item<1, 3-> Berechne die \alert{unterscheidbaren} Zustände + \item<1, 6-> \alert{Kollabiere} die äquivalenten Zustände + \end{enumerate} + \end{block} + + \vfill + + \begin{columns}[c]<2-> + \begin{column}{.5\textwidth}<3-> + \begin{center} + \begin{tabu}to .8\textwidth{|X[c]|X[c]|X[c]|X} + \multicolumn{2}{l}{0} \\ \tabucline{1-1} + \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} & \multicolumn{2}{l}{1} \\ \tabucline{1-2} + \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} & & \multicolumn{2}{l}{2} \\ \tabucline{1-3} + \alt<-3>{}{\textcolor{tumred}{$\times$}} & \alt<-3>{}{\textcolor{tumred}{$\times$}}& \alt<-3>{} {\textcolor{tumred}{$\times$}}& 3 \\ \tabucline{1-3} + \end{tabu} + \end{center} + \end{column} + \begin{column}{.5\textwidth} + \begin{tikzpicture}[automaton, node distance=2.5cm] + \useasboundingbox (-0.5, -0.5) rectangle (2, -2); + + \node[state, initial] (q0) {$q_0$}; + \node<-5>[state] (q1) [right of = q0] {$q_1$}; + \node<-5>[state] (q2) [below of = q0] {$q_2$}; + \node<6>[state, fill=tumred!40] (q12) [right of = q0] {$q_{12}$}; + \node[state, accepting] (q3) [right of = q2] {$q_3$}; + + \draw<-5>[->] (q0) edge node {$a$} (q1); + \draw<-5>[->] (q0) edge node {$b$} (q2); + \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} + \end{column} + \end{columns} +\end{frame} +} + +\defineUnit{regulaeresprachen}{% +\begin{frame} + \frametitle{Reguläre Sprachen} + \setbeamercovered{dynamic} + + \begin{center} + \begin{tikzpicture}[node distance=2cm] + \node (nfa) {NFA}; + \node (dfa) [left of=nfa] {DFA}; + \node (enfa) [right of=nfa] {$\epsilon$-NFA}; + \node (re) [below of=nfa] {RE}; + + \draw [every edge] (nfa) -- (dfa); + \draw [every edge] (enfa) -- (nfa); + \draw [every edge] (dfa) -- (re); + \draw [every edge] (nfa) -- (re); + \draw [every edge] (re) -- (enfa); + \end{tikzpicture} + \end{center} + + \vfill + \pause + + \begin{theorem} + Für eine Darstellung $D$ einer regulären Sprache ist \alert{entscheidbar}: + \vspace{1em} + \begin{description} + \item[Wortproblem] Gegeben $w$, gilt $w \in L(D)$? + \item[Leerheitsproblem] Ist $L(D) = \emptyset$? + \item[Endlichkeitsproblem] Ist $|L(D)| < \infty$? + \item[Äquivalenzproblem] Gilt $L(D_1) = L(D_2)$? + \end{description} + \end{theorem} +\end{frame} +}
--- a/notes/tex/computation.tex Thu Jul 11 21:25:21 2013 +0200 +++ b/notes/tex/computation.tex Thu Jul 11 21:57:50 2013 +0200 @@ -120,6 +120,28 @@ \end{frame} } +\defineUnit{ndtm}{% +\begin{frame} + \frametitle{Nichtdeterministische TM} + \setbeamercovered{dynamic} + + \begin{definition}[Nichtdeterministische Turingmaschine] + Eine \alert{nichtdeterministische} Turingmaschine (TM) ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem + \begin{itemize} + \item \ldots + \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to \mathcal{P} \left( Q \times \Gamma \times \left\{ L, R, N \right\} \right)$ + \item \ldots + \end{itemize} + \end{definition} + + \vfill + + \begin{theorem} + Zu jeder nichtdeterministischen TM $N$ gibt es eine deterministische TM $M$ mit \alert{$L(N) = L(M)$}. + \end{theorem} +\end{frame} +} + \defineUnit{chomsky}{% \begin{frame}[c] \frametitle{Chomsky-Hierarchie} @@ -471,6 +493,28 @@ \end{frame} } +\defineUnit{breduktion}{% +\begin{frame} + \frametitle{Reduzierbarkeit} + \setbeamercovered{dynamic} + + \begin{definition}[Reduzierbarkeit] + Eine Menge $A \subseteq \Sigma^*$ ist \alert{reduzierbar} auf eine Menge $B \subseteq \Gamma^*$ gdw es eine totale und berechenbare Funktion $f:\Sigma^* \to \Gamma^*$ gibt mit + \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\] + Wir schreiben dann \alert{$A \leq B$}. + \end{definition} + + \vfill + + \structure{Intuition}: + \begin{itemize} + \item $B$ ist \alert{mindestens so schwer} zu lösen wie $A$ + \item Ist $A$ unlösbar, dann auch $B$. + \item Ist $B$ unlösbar, dann erst recht $A$. + \end{itemize} +\end{frame} +} + \defineUnit{spezielleshalteproblem}{% \begin{frame} \frametitle{Spezielles Halteproblem}
--- a/notes/tex/grammars.tex Thu Jul 11 21:25:21 2013 +0200 +++ b/notes/tex/grammars.tex Thu Jul 11 21:57:50 2013 +0200 @@ -64,6 +64,33 @@ \end{frame} } +\defineUnit{induktivesprachdefinition}{% +\begin{frame} + \frametitle{Induktive Sprachdefinition} + \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. + \end{block} + + \begin{example}[Vorbereitung 3] + Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$: + + \begin{align*} + 1 &\in L_G(S) \\ + u \in L_G(S) \quad \Longrightarrow \quad 0\alert{u}1 &\in L_G(S) \\ + u \in L_G(S) \quad \Longrightarrow \quad \alert{u}11 &\in L_G(S) + \end{align*} + + Also z.B: + + \[ + 1 \in L_G(S) \Longrightarrow 0\alert{1}0 \in L_G(S) \Longrightarrow \alert{010}11 \in L_G(S) + \] + \end{example} +\end{frame} +} + \defineUnit{cnf}{% \begin{frame} \frametitle{CNF} @@ -173,6 +200,76 @@ \end{frame} } +\defineUnit{cfpl}{% +\begin{frame} + \frametitle{Pumping Lemma für CFLs} + \setbeamercovered{dynamic} + + \begin{theorem}[Pumping Lemma für kontextfreie Sprachen] + Sei $L \subseteq \Sigma^*$ kontextfrei. Dann gibt es ein $n > 0$, so dass sich \alert{jedes} $z \in L$ mit $|z| \geq n$ so in \alert{$z = uvwxy$} zerlegen lässt, dass + \begin{itemize} + \item $vx \alert{\neq \epsilon}$ + \item $|vwx| \alert{\leq n}$ + \item $\forall i \alert{\geq 0}. uv^iwx^iy \in L$ + \end{itemize} + \end{theorem} + + \vfill + + \begin{center} + \begin{columns} + \begin{column}{.4\textwidth} + \begin{tikzpicture} + \coordinate (outer) at (2, 2.4); + \coordinate (middle) at (2.2, 1.2); + \coordinate (inner) at (2.2, 0.6); + % outer + \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0); + % middle + \draw[fill=tumgreen!40] (1.2, 0) -- (1.7, 0) -- (inner) -- (2.7, 0) -- (3.2, 0) -- (middle) -- (1.2, 0); + % inner + \draw[fill=tumblue!40] (1.7, 0) -- (inner) -- (2.7, 0) -- (1.7, 0); + + % path + \draw[dashed, thick] (outer) -- (middle) -- (inner); + \draw[fill] (outer) circle (1pt); + \draw[fill] (middle) circle (1pt); + \draw[fill] (inner) circle (1pt); + + % nodes + \node[below] at (0.6, 0) {$u$}; + \node[below] at (1.45, 0) {$v$}; + \node[below] at (2.2, 0) {$w$}; + \node[below] at (2.95, 0) {$x$}; + \node[below] at (3.6, 0) {$y$}; + \end{tikzpicture} + \end{column} + \begin{column}{.4\textwidth} + \begin{tikzpicture} + \coordinate (outer) at (2, 2.4); + \coordinate (middle) at (2.2, 1.2); + \coordinate (inner) at (2.2, 0.6); + % outer + \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0); + % inner + \draw[fill=tumblue!40] (1.7, 0.6) -- (middle) -- (2.7, 0.6) -- (1.7, 0.6); + + % path + \draw[dashed, thick] (outer) -- (middle); + \draw[fill] (outer) circle (1pt); + \draw[fill] (middle) circle (1pt); + + % nodes + \node[below] at (0.6, 0) {$u$}; + \node[below] at (2.2, 0) {$w$}; + \node[below] at (3.6, 0) {$y$}; + \end{tikzpicture} + \end{column} + \end{columns} + \end{center} +\end{frame} +} + \defineUnit{cyk}{% \begin{frame} \frametitle{CYK} @@ -308,3 +405,48 @@ \end{example} \end{frame} } + +\defineUnit{kontextfreiesprachen}{% +\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} +}