BuK/IIm11/Studenten/sirorose/utm

Aus ProgrammingWiki
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)

 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

= 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 ==

 $\delta(q_0,1) = (q_0,1,R) \mathrel{\widehat{=}} 1011011011011\text{   0}$ 
 $\delta(q_1,0) = (q_0,0,L) \mathrel{\widehat{=}} 1101010101\text{   0}$ 
 $\delta(q_1,1) = (q_2,1,R) \mathrel{\widehat{=}} 110110111011011\text{   0}$ 
 $\delta(q_2,1) = (q_0,1,L) \mathrel{\widehat{=}} 1110110101101\text{   00   1011}$ 

{| 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
BuK/IIm11/Studenten/sirorose/utm

Suche
