Mercurial > 14ss.theoinf
changeset 30:b56fe50e0132
nineth sheet and notes
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Sat, 21 Jun 2014 20:11:55 +0200 |
parents | 27fd7a9cee49 |
children | 777563904120 |
files | notes/complete_notes.pdf notes/tex/complete_notes.tex notes/tex/computation.tex notes/tex/ue09_notes.tex notes/ue09_notes.pdf ue09.pdf |
diffstat | 6 files changed, 54 insertions(+), 1 deletions(-) [+] |
line wrap: on
line diff
--- 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}
--- 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}
--- /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}