BuK/IIm14/Studenten/s3ankrau1/utm

Wiki-Quelltext dieser Seite.

<language>Java</language>
= Universelle Turingmaschine =

'''(1) Verwenden Sie kfG Edit aus AtoCC, um die folgende kontextfreie Grammatik G für die Sprache der TM-Codierungen zu definieren.'''

<code id="557c0d476219d">G = (N, T, P, s)

N = {TMcodierung, Trenner, Endzustaende, Delta, Uebergang, Kopfbewegung, L, R, N, Zeichen, Null, Eins, B, Zustand, Einsenfolge}
T = {0, 1}
P = {
   TMcodierung  -> Delta Trenner Endzustaende 
   Trenner      -> 0 0 
   Endzustaende -> Zustand 0 Endzustaende 
                 | Zustand 
   Delta        -> Uebergang 0 Delta | Uebergang 
   Uebergang    -> Zustand 0 Zeichen 0 Zustand 0 Zeichen 0 Kopfbewegung 
   Kopfbewegung -> L | R | N 
   L            -> 1 
   R            -> 1 1 
   N            -> 1 1 1 
   Zeichen      -> Null | Eins | B 
   Null         -> 1 
   Eins         -> 1 1 
   B            -> 1 1 1 
   Zustand      -> Einsenfolge 
   Einsenfolge  -> 1 | 1 Einsenfolge 
}
s = TMcodierung
</code>


----


'''(2) Als Beispiel betrachten wir die Turingmaschine'''

$M = (\{q_{0},q_{1},q_{2}\},\{\text{0},\text{1}\},\{\$,\text{0},\text{1}\},\delta,q_{0},\$,\{q_{0},q_{1}\})$

[[Bild:Tm-codierung nka.jpg|400px]]

[[Bild:Tm-codierung nka transition.jpg|400px]]

Verwenden Sie AutoEdit (aus AtoCC) und simulieren Sie die Anwendung von $M$ auf
diverse Eingabewörter. Darunter sollte es Wörter $w$ geben, für die $M(w)$

* in einem Endzustand stoppt ($\epsilon$, 0, 1, 0101010110),
* in einem Nicht-Endzustand stoppt (11, 111, 1111),
* nicht stoppt (10).

Schauen Sie sich auch den Übergangsgraph von $M$ an.


----


Kodieren Sie $M$ aus dem Beispiel per Hand, indem Sie die folgenden Kodierungsregeln befolgen:

{| cellpadding="6" cellspacing="0" border="1"
|'''Symbol'''
|'''Kodierung'''
|-
|0
|1
|-
|1
|11
|-
|B
|111
|-
|$q_0$
|1
|-
|$q_1$
|11
|-
|$\vdots$
|$\vdots$
|-
|$q_n$
|$1^{n+1}$
|-
|L
|1
|-
|R
|11
|-
|N
|111
|}