# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1403374315 -7200
# Node ID b56fe50e0132b3344533f4f69a4c8cb6f40d8b74
# Parent  27fd7a9cee4912bec0255d4418277a41de7e0f54
nineth sheet and notes

diff -r 27fd7a9cee49 -r b56fe50e0132 notes/complete_notes.pdf
Binary file notes/complete_notes.pdf has changed
diff -r 27fd7a9cee49 -r b56fe50e0132 notes/tex/complete_notes.tex
--- a/notes/tex/complete_notes.tex	Sat Jun 21 20:10:47 2014 +0200
+++ b/notes/tex/complete_notes.tex	Sat Jun 21 20:11:55 2014 +0200
@@ -64,4 +64,13 @@
 \showUnit{tmkonfiguration}
 \showUnit{ndtm}
 \showUnit{lba}
+
+%ue09
+\showUnit{queueautomaten}
+\showUnit{regulaeresprachen}
+\showUnit{kontextfreiesprachen}
+\showUnit{typ0sprachen}
+\showUnit{spracheigenschaften}
+\showUnit{chomsky}
+\showUnit{formalesprachen}
 \end{document}
diff -r 27fd7a9cee49 -r b56fe50e0132 notes/tex/computation.tex
--- a/notes/tex/computation.tex	Sat Jun 21 20:10:47 2014 +0200
+++ b/notes/tex/computation.tex	Sat Jun 21 20:11:55 2014 +0200
@@ -146,7 +146,7 @@
 \begin{frame}
     \frametitle{Linear Beschränkte Automaten}
 
-    \begin{definition}[Linear Beschränkte Automaten]
+    \begin{definition}[Linear Beschränkte Automat]
         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}
 
@@ -158,6 +158,33 @@
 \end{frame}
 }
 
+\defineUnit{queueautomaten}{%
+\begin{frame}
+    \frametitle{Queue-Automaten}
+
+    \begin{definition}[Queue-Automat]
+        Ein \structure{Queue-Automat (QA)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ die analog zu Kellerautomaten definiert sind.
+        \begin{itemize}
+            \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$
+        \end{itemize}
+        Im Gegensatz zu PDAs werden neue Symbole \alert{hinten} angefügt.
+    \end{definition}
+
+    \begin{example}[]
+        Gegeben sei die Konfiguration $(q, a, \structure{x\alpha})$ eines Queue-Automaten und ein Schritt der Übergangsfunktion.
+        \begin{align}
+            \delta(q, a, \structure{x}) &= (q^\prime, \alert{yz}) \\
+            \intertext{Dann ergibt sich die folgende Transition.}
+            (q, a, \structure{x\alpha}) &\to (q^\prime, \epsilon, \structure{\alpha}\alert{yz})
+        \end{align}
+    \end{example}
+
+    \begin{theorem}[]
+        Queue-Automaten sind genauso mächtig wie Turingmaschinen.
+    \end{theorem}
+\end{frame}
+}
+
 \defineUnit{chomsky}{%
 \begin{frame}[c]
     \frametitle{Chomsky-Hierarchie}
diff -r 27fd7a9cee49 -r b56fe50e0132 notes/tex/ue09_notes.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue09_notes.tex	Sat Jun 21 20:11:55 2014 +0200
@@ -0,0 +1,17 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 9: Turingmaschinen II}
+\subtitle{Theoretische Informatik Sommersemester 2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{queueautomaten}
+\showUnit{regulaeresprachen}
+\showUnit{kontextfreiesprachen}
+\showUnit{typ0sprachen}
+\showUnit{spracheigenschaften}
+\showUnit{chomsky}
+\showUnit{formalesprachen}
+\end{document}
diff -r 27fd7a9cee49 -r b56fe50e0132 notes/ue09_notes.pdf
Binary file notes/ue09_notes.pdf has changed
diff -r 27fd7a9cee49 -r b56fe50e0132 ue09.pdf
Binary file ue09.pdf has changed