Mercurial > 14ss.theoinf

changeset 27:f7bcd68a0c12

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
eigth sheet and notes; add hierarchy slides
author Markus Kaiser <markus.kaiser@in.tum.de>
date Fri, 06 Jun 2014 17:13:58 +0200
parents c7069de7eb0f
children 2e1a4e52da10
files notes/complete_notes.pdf notes/hierarchy.pdf notes/tex/automata.tex notes/tex/complete_notes.tex notes/tex/computation.tex notes/tex/grammars.tex notes/tex/hierarchy.tex notes/tex/preamble.tex notes/tex/ue07_notes.tex notes/tex/ue08_notes.tex notes/ue07_notes.pdf notes/ue08_notes.pdf ue08.pdf
diffstat 13 files changed, 102 insertions(+), 41 deletions(-) [+]
line wrap: on
line diff
Binary file notes/complete_notes.pdf has changed
Binary file notes/hierarchy.pdf has changed
--- a/notes/tex/automata.tex	Sun Jun 01 00:30:12 2014 +0200
+++ b/notes/tex/automata.tex	Fri Jun 06 17:13:58 2014 +0200
@@ -671,13 +671,14 @@
         \begin{tikzpicture}[node distance=2cm]
             \node (nfa) {NFA};
             \node (dfa) [left of=nfa] {DFA};
+            \node (lg) [left of=dfa] {RLG};
             \node (enfa) [right of=nfa] {$\epsilon$-NFA};
             \node (re) [below of=nfa] {RE};
 
+            \draw [every edge, <->] (lg) -- (dfa);
             \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}
@@ -687,7 +688,7 @@
     \begin{theorem}
         Für eine Darstellung $D$ einer regulären Sprache ist \alert{entscheidbar}:
         \vspace{1em}
-        \begin{description}
+        \begin{description}[Endlichkeitsproblem\quad]
             \item[Wortproblem] Gegeben $w$, gilt $w \in L(D)$?
             \item[Leerheitsproblem] Ist $L(D) = \emptyset$?
             \item[Endlichkeitsproblem] Ist $|L(D)| < \infty$?
--- a/notes/tex/complete_notes.tex	Sun Jun 01 00:30:12 2014 +0200
+++ b/notes/tex/complete_notes.tex	Fri Jun 06 17:13:58 2014 +0200
@@ -57,4 +57,11 @@
 %ue07
 \showUnit{dpda}
 \showUnit{lrgrammars}
+
+%ue08
+\showUnit{tmdefinition}
+\showUnit{tmvisualisierung}
+\showUnit{tmkonfiguration}
+\showUnit{ndtm}
+\showUnit{lba}
 \end{document}
--- a/notes/tex/computation.tex	Sun Jun 01 00:30:12 2014 +0200
+++ b/notes/tex/computation.tex	Fri Jun 06 17:13:58 2014 +0200
@@ -4,15 +4,15 @@
     \setbeamercovered{dynamic}
 
     \begin{definition}[Turingmaschine]
-        Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
+        Eine deterministische \structure{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
         \begin{itemize}
-            \item endlichen Menge von \alert{Zuständen} $Q$
-            \item endlichen \alert{Eingabealphabet} $\Sigma$
-            \item endlichen \alert{Bandalphabet} $\Gamma$ mit $\Sigma \subset \Gamma$
-            \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
-            \item \alert{Startzustand} $q_0 \in Q$
-            \item \alert{Leerzeichen} $\square \in \Gamma \setminus \Sigma$
-            \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{Bandalphabet} $\Gamma$ mit $\Sigma \subset \Gamma$
+            \item \structure{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
+            \item \structure{Startzustand} $q_0 \in Q$
+            \item \structure{Leerzeichen} $\square \in \Gamma \setminus \Sigma$
+            \item Menge von \structure{Endzuständen} $F \subseteq Q$
         \end{itemize}
     \end{definition}
 \end{frame}
@@ -24,9 +24,9 @@
     \setbeamercovered{dynamic}
 
     \begin{definition}[Turingmaschine]
-        Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
+        Eine deterministische \structure{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
         \begin{itemize}
-            \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
+            \item \structure{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
         \end{itemize}
     \end{definition}
 
@@ -70,14 +70,14 @@
     \setbeamercovered{dynamic}
 
     \begin{definition}[Konfiguration]
-        Eine \alert{Konfiguration} ist ein Tripel $(\alpha, q, \beta) \in \Gamma^* \times Q \times \Gamma^*$. \\
+        Eine \structure{Konfiguration} ist ein Tripel $(\alpha, q, \beta) \in \Gamma^* \times Q \times \Gamma^*$. \\
         Dies modelliert eine TM mit:
         \begin{itemize}
-            \item \alert{Bandinhalt} $\ldots\square\alpha\beta\square\ldots$
-            \item \alert{Zustand} $q$
-            \item Kopf auf dem \alert{ersten Zeichen} von $\beta\square$
+            \item \structure{Bandinhalt} $\ldots\square\alpha\beta\square\ldots$
+            \item \structure{Zustand} $q$
+            \item Kopf auf dem \structure{ersten Zeichen} von $\beta\square$
         \end{itemize}
-        Die \alert{Startkonfiguration} bei Eingabe $w \in \Sigma^*$ ist $(\epsilon, q_0, w)$.
+        Die \structure{Startkonfiguration} bei Eingabe $w \in \Sigma^*$ ist $(\epsilon, q_0, w)$.
     \end{definition}
 
     \vfill
@@ -113,7 +113,7 @@
 
     \only<2> {
         \begin{definition}[Akzeptanz]
-            Eine TM $M$ \alert{akzeptiert} die Sprache
+            Eine TM $M$ \structure{akzeptiert} die Sprache
             \[ L(M) = \left\{ w \in \Sigma^* \mid \exists \alert{f \in F}, \alpha, \beta \in \Gamma^* . (\epsilon, q_0, w) \rightarrow_M^* (\alpha, \alert{f}, \beta) \right\} \]
         \end{definition}
     }
@@ -126,10 +126,10 @@
     \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
+        Eine \structure{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 \structure{Ü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}
@@ -142,6 +142,22 @@
 \end{frame}
 }
 
+\defineUnit{lba}{%
+\begin{frame}
+    \frametitle{Linear Beschränkte Automaten}
+
+    \begin{definition}[Linear Beschränkte Automaten]
+        Eine TM heißt \structure{linear beschränkt (LBA)}, wenn sie den Bereich des Bandes, auf dem das Eingabewort steht, niemals verlässt.
+    \end{definition}
+
+    \vfill
+
+    \begin{theorem}[]
+        Die \structure{linear beschränkten NDTMs} akzeptieren genau die Klasse der \alert{kontextsensitiven Sprachen (Typ 1)}.
+    \end{theorem}
+\end{frame}
+}
+
 \defineUnit{chomsky}{%
 \begin{frame}[c]
     \frametitle{Chomsky-Hierarchie}
@@ -153,10 +169,10 @@
             \tikzstyle{caption} = [align=left, anchor=north west];
 
             \chomsky{tumlightblue}{}{0}{Alle formalen Sprachen};
-            \chomsky{tumred}{}{1}{Typ 0 - Rekursiv aufzählbar\\Grammatik};
-            \chomsky{tumblue}{}{2}{Typ 1 - Kontextsensitiv\\Längenmonotone Grammatik};
-            \chomsky{tumorange}{}{3}{Typ 2 - Kontextfrei\\Links nur ein Nichtterminal};
-            \chomsky{tumgreen}{}{4}{Typ 3 - Regulär\\Links- / Rechtsreguläre Grammatik};
+            \chomsky{tumred}{}{1}{Typ 0 - Rekursiv aufzählbar\\Grammatik\\Turingmaschine, WHILE-Programm, $\mu$-rekursive Funktion};
+            \chomsky{tumblue}{}{2}{Typ 1 - Kontextsensitiv\\Längenmonotone Grammatik\\Linear Beschränkter Automat (LBA)};
+            \chomsky{tumorange}{}{3}{Typ 2 - Kontextfrei\\Links nur ein Nichtterminal\\Kellerautomat (PDA)};
+            \chomsky{tumgreen}{}{4}{Typ 3 - Regulär\\Links- / Rechtsreguläre Grammatik\\DFA, NFA, RE};
         \end{tikzpicture}
     \end{center}
 \end{frame}
@@ -954,14 +970,14 @@
     \vfill
 
     \begin{theorem}[]
-        Sei $A$ formale Sprache, dann ist äuqivalent:
+        Sei $A$ formale Sprache, dann ist äquivalent:
         \vspace{1em}
         \begin{itemize}
-            \item $A$ ist \alert{Typ 0 Sprache}
-            \item $A$ \alert{rekursiv aufzählbar}
-            \item $A$ \alert{semi-entscheidbar}, also $\chi'_A$ berechenbar
-            \item $A=L(M)$ für eine \alert{TM $M$}
-            \item $A$ ist \alert{Bild oder Urbild} einer berechenbaren Funktion
+            \item $A$ ist \structure{Typ 0 Sprache}
+            \item $A$ \structure{rekursiv aufzählbar}
+            \item $A$ \structure{semi-entscheidbar}, also $\chi'_A$ berechenbar
+            \item $A=L(M)$ für eine \structure{TM $M$}
+            \item $A$ ist \structure{Bild oder Urbild} einer berechenbaren Funktion
         \end{itemize}
     \end{theorem}
 \end{frame}
@@ -973,13 +989,14 @@
     \setbeamercovered{dynamic}
 
     \begin{itemize}
-        \item \alert{Abschlusseigenschaften}
+        \item 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\\
+            CSL & ja & ja & ja & ja & ja\\
             TM & \structure{ja} & \structure{ja} & \structure{nein} & \structure{ja} & \structure{ja}
         \end{tabu}
     \end{table}
@@ -987,13 +1004,14 @@
     \vfill
 
     \begin{itemize}
-        \item \alert{Entscheidbarkeit}
+        \item 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\\
+            CSL & $\Oh(2^n)$ & nein & nein & nein\\
             TM & \structure{nein} & \structure{nein} & \structure{nein} & \structure{nein}
         \end{tabu}
     \end{table}
@@ -1010,12 +1028,13 @@
             \tikzstyle{rect} = [thick];
             \tikzstyle{caption} = [align=left, anchor=north west];
 
-            \langclass{brown}{}{0}{Formale Sprache - $\Sigma^*$};
+            \definecolor{hannahyellow}{HTML}{FFB81C}
+            \langclass{brown}{}{0}{Formale Sprache $\subseteq \Sigma^*$};
             \langclass{tumblue}{}{1}{Typ 0 - Semi-Entscheidbar};
             \langclass{tumgreen}{}{2}{Entscheidbar};
             \langclass{violet}{}{3}{LOOP, PR};
             \langclass{tumred}{}{4}{NP};
-            \langclass{tumorange}{dashed}{5}{P};
+            \langclass{hannahyellow}{dashed}{5}{P};
             \langclass{tumgreen!40!black}{}{6}{Typ 2 - Kontextfrei};
             \langclass{tumlightblue!80!black}{}{7}{Typ 3 - Regulär};
             \langclass{tumblue!20!black}{}{8}{Endlich};
--- a/notes/tex/grammars.tex	Sun Jun 01 00:30:12 2014 +0200
+++ b/notes/tex/grammars.tex	Fri Jun 06 17:13:58 2014 +0200
@@ -763,19 +763,22 @@
         \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$};
+            \node (GNF) [right of = CNF] {GNF};
+            \node (PDAf) [below = 1.5cm of GNF] {PDA$_F$};
+            \node (PDAe) [below = 1.5cm of CNF] {PDA$_\epsilon$};
 
             \draw [every edge, <->] (CFG) -- (CNF);
-            \draw [every edge, <->] (CNF) -- (PDAe);
+            \draw [every edge, ->] (CNF) -- (GNF);
+            \draw [every edge, ->] (GNF) -- (PDAe);
             \draw [every edge, <->] (PDAe) -- (PDAf);
+            \draw [every edge, ->] (PDAe) -- (CFG);
         \end{tikzpicture}
     \end{center}
 
     \vfill
 
     \begin{itemize}
-        \item \alert{Abschlusseigenschaften}
+        \item Abschlusseigenschaften
     \end{itemize}
     \begin{table}
         \begin{tabu}to \textwidth{X[c]|ccccc}
@@ -786,7 +789,7 @@
     \end{table}
 
     \begin{itemize}
-        \item \alert{Entscheidbarkeit}
+        \item Entscheidbarkeit
     \end{itemize}
     \begin{table}
         \begin{tabu}to \textwidth{X[c]|cccc}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/hierarchy.tex	Fri Jun 06 17:13:58 2014 +0200
@@ -0,0 +1,16 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Chomsky Hierarchie Übersicht}
+\subtitle{Theoretische Informatik Sommersemester 2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{regulaeresprachen}
+\showUnit{kontextfreiesprachen}
+\showUnit{typ0sprachen}
+\showUnit{spracheigenschaften}
+\showUnit{chomsky}
+\showUnit{formalesprachen}
+\end{document}
--- a/notes/tex/preamble.tex	Sun Jun 01 00:30:12 2014 +0200
+++ b/notes/tex/preamble.tex	Fri Jun 06 17:13:58 2014 +0200
@@ -82,5 +82,5 @@
 \tikzstyle{machine} = [rectangle, draw, minimum width=2cm, minimum height=1cm, inner sep=3mm, fill=tumgreen!10]
 
 \newcommand{\pcp}[2]{ \begin{tabu}{c} #1 \\ \tabucline{-} #2 \\ \end{tabu} }
-\newcommand{\chomsky}[4]{\draw[rect, #1, fill=#1!10, #2] ({5.5 - #3 * 0.5}, {0 + #3 * 0.3}) rectangle ({-5.5 + #3 * 0.5}, {7 - #3 * 1.2}) node[caption] {#4};}
+\newcommand{\chomsky}[4]{\draw[rect, #1, fill=#1!10, #2] ({5.2 - #3 * 0.5}, {0 + #3 * 0.15}) rectangle ({-5.2 + #3 * 0.5}, {8 - #3 * 1.5}) node[caption] {#4};}
 \newcommand{\langclass}[4]{\draw[rect, #1, fill=#1!20, #2] ({5.2 - #3 * 0.5}, {0 + #3 * 0.12}) rectangle ({-5.2 + #3 * 0.5}, {7.5 - #3 * 0.75}) node[caption] {#4};}
--- a/notes/tex/ue07_notes.tex	Sun Jun 01 00:30:12 2014 +0200
+++ b/notes/tex/ue07_notes.tex	Fri Jun 06 17:13:58 2014 +0200
@@ -1,7 +1,7 @@
 \input{preamble.tex}
 \input{frames.tex}
 
-\title{Übung 6: DPDAs und LR-Grammatiken}
+\title{Übung 7: DPDAs und LR-Grammatiken}
 \subtitle{Theoretische Informatik Sommersemester 2014}
 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue08_notes.tex	Fri Jun 06 17:13:58 2014 +0200
@@ -0,0 +1,15 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 8: Turingmaschinen}
+\subtitle{Theoretische Informatik Sommersemester 2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{tmdefinition}
+\showUnit{tmvisualisierung}
+\showUnit{tmkonfiguration}
+\showUnit{ndtm}
+\showUnit{lba}
+\end{document}
Binary file notes/ue07_notes.pdf has changed
Binary file notes/ue08_notes.pdf has changed
Binary file ue08.pdf has changed