BuK/IIm11/Studenten/sirorose/utm

Wiki-Quelltext dieser Seite.

=== Grammatik ===

Verwenden Sie kfG Edit aus AtoCC, um die folgende kontextfreie Grammatik G fur die Sprache der TM-Codierungen zu definieren. G = (N, T, P, s)

 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 -> N | R | L
 L -> 1
 R -> 1 1
 N -> 1 1 1
 Zeichen -> B | Eins | Null
 Null -> 1
 Eins -> 1 1
 B -> 1 1 1
 Zustand -> Einsenfolge
 Einsenfolge -> 1 | 1 Einsenfolge

= Beispiel-Maschine =

== Definition ==

$ M = (\{q_0, q_1, q_2\}, \{0, 1\}, \{\$, 0, 1\}, \$, q_0, \$, \{q_0, q_1\}) $

= Übergangsgraph =
[[Bild:Sirorose_Bildschirmfoto_2012-05-03_um_19.32.33.png]]

== Kodierte Beispiel-Maschine ==

{| border="1" cellpadding="5" cellspacing="0"
!Symbol
!Kodierung	
|-
|| 0 || 1
|-
|| 1 || 11
|-
|| $q_0$ || 1
|-
|| $q_1$ || 11
|-
|| $q_2$ || 111
|-
|| L || 1
|-
|| R || 11
|-
|| N || 111
|-
|}


Anhand der vorgegebenen Kodierungvorschrift ergibt sich folgendes Wort für die Turing-Maschine:

101101101101101101010101011011011101101101110110101101001011