---

Geschrieben von InformatikSpaß95 am 25.11.2014 um 14:59:

  Grammatik in Kellerautomat konvertieren

Hallo,
ich habe ein Problem mit einer meiner Aufgaben.
Ich soll diese Grammatik:
(S ist das Startsymbol)

S -> XSX | TXa
T -> TXT | X | epsilon
X -> aa | Ta | b

in einen Kellerautomat umwandeln.
Ich habe es mal versucht:

q0, Epsilon ,S -> q0, XSX
q0, Epsilon, S -> q0, TXa

q0, Epsilon, T -> q0, TXT
q0, Epsilon, T -> q0, X
q0, Epsilon, T -> q0, epsilon

q0, Epsilon, X -> q0, aa
q0, Epsilon, X -> q0, Ta
q0, Epsilon, X -> q0, b

q0, a, a -> q0, Epsilon
q0, b, b -> q0, Epsilon

Wird so gelesen:
Befinde mich im Zustand q0, lese ein Epsilon, sehe in S -> bleibe im q0, schreibe ein XSX
Ich glaube allerdings das ich mehr als einen Zustand brauche da T und X ja keine Startzustände sind aber wie mache ich das dann?