Mercurial > 14ss.theoinf
comparison notes/tex/computation.tex @ 30:b56fe50e0132
nineth sheet and notes
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Sat, 21 Jun 2014 20:11:55 +0200 |
| parents | f7bcd68a0c12 |
| children | 777563904120 |
comparison
equal
deleted
inserted
replaced
| 29:27fd7a9cee49 | 30:b56fe50e0132 |
|---|---|
| 144 | 144 |
| 145 \defineUnit{lba}{% | 145 \defineUnit{lba}{% |
| 146 \begin{frame} | 146 \begin{frame} |
| 147 \frametitle{Linear Beschränkte Automaten} | 147 \frametitle{Linear Beschränkte Automaten} |
| 148 | 148 |
| 149 \begin{definition}[Linear Beschränkte Automaten] | 149 \begin{definition}[Linear Beschränkte Automat] |
| 150 Eine TM heißt \structure{linear beschränkt (LBA)}, wenn sie den Bereich des Bandes, auf dem das Eingabewort steht, niemals verlässt. | 150 Eine TM heißt \structure{linear beschränkt (LBA)}, wenn sie den Bereich des Bandes, auf dem das Eingabewort steht, niemals verlässt. |
| 151 \end{definition} | 151 \end{definition} |
| 152 | 152 |
| 153 \vfill | 153 \vfill |
| 154 | 154 |
| 155 \begin{theorem}[] | 155 \begin{theorem}[] |
| 156 Die \structure{linear beschränkten NDTMs} akzeptieren genau die Klasse der \alert{kontextsensitiven Sprachen (Typ 1)}. | 156 Die \structure{linear beschränkten NDTMs} akzeptieren genau die Klasse der \alert{kontextsensitiven Sprachen (Typ 1)}. |
| 157 \end{theorem} | |
| 158 \end{frame} | |
| 159 } | |
| 160 | |
| 161 \defineUnit{queueautomaten}{% | |
| 162 \begin{frame} | |
| 163 \frametitle{Queue-Automaten} | |
| 164 | |
| 165 \begin{definition}[Queue-Automat] | |
| 166 Ein \structure{Queue-Automat (QA)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ die analog zu Kellerautomaten definiert sind. | |
| 167 \begin{itemize} | |
| 168 \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ | |
| 169 \end{itemize} | |
| 170 Im Gegensatz zu PDAs werden neue Symbole \alert{hinten} angefügt. | |
| 171 \end{definition} | |
| 172 | |
| 173 \begin{example}[] | |
| 174 Gegeben sei die Konfiguration $(q, a, \structure{x\alpha})$ eines Queue-Automaten und ein Schritt der Übergangsfunktion. | |
| 175 \begin{align} | |
| 176 \delta(q, a, \structure{x}) &= (q^\prime, \alert{yz}) \\ | |
| 177 \intertext{Dann ergibt sich die folgende Transition.} | |
| 178 (q, a, \structure{x\alpha}) &\to (q^\prime, \epsilon, \structure{\alpha}\alert{yz}) | |
| 179 \end{align} | |
| 180 \end{example} | |
| 181 | |
| 182 \begin{theorem}[] | |
| 183 Queue-Automaten sind genauso mächtig wie Turingmaschinen. | |
| 157 \end{theorem} | 184 \end{theorem} |
| 158 \end{frame} | 185 \end{frame} |
| 159 } | 186 } |
| 160 | 187 |
| 161 \defineUnit{chomsky}{% | 188 \defineUnit{chomsky}{% |