|
M = (Q,S,G,d,q0,B,F)
- Q = {a0, q1, q2, q3, q4}
- F = {q4}
- S = {a, b}
- G = {a, b, B}
- d = {
d(q0,a) = (q0,a,R),
d(q0,b) = (q1,b,R),
d(q1,a) = (q2,b,L),
d(q1,B) = (q3,B,L),
d(q2,b) = (q0,a,R),
d(q3,b) = (q4,b,S),
}
Welche Sprache akzeptiert M? Was passiert bei Wörtern, die nicht zur Sprache der TM gehören?
|
Auch eine TM kann als Graph dargestellt werden. Dabei ist das Label der Kanten dreigeteilt.
Es enthält in der ersten Komponente das aktuelle Eingabezeichen,
an zweiter Stelle folgt das Zeichen, das in die Zelle des Arbeitsbandes geschrieben werden soll.
Die letzte Position bezeichnet die Aktion des Lese-/Schreibkopfes.
|
|
|
|
1
2
3
4
5
Sprache
