Hallo,
ich wollte mal aus Spaß einen Kellerautomaten_ entwerfen, der einen Klammerausdruck verifiziert.
Sigma ist logischerweise {"(",")"}, Kelleralphabet {"/", "(", ")"}, Zustände {"Zin", "Zno", "Zyes", "Zend"}, # = "/", q0 = "Zin", F {"Zyes}, delta = Zustände x (Sigma vereinigt mit epsilon) x Kelleralphabet
mit f(eingabeZeichen, momentanerZustand) und g(stack.pop), wobei eben f und g benutzerdefinierte Funktionen sind.
Die Zeichnung dazu:
Ist das so korrekt?
Erklärung:
Automat befindet sich im Zustand Zin, wird ein "(" gelesen unter der Bedingung, dass das oberste Element des Stacks "\" (q0) ist, dann wechsle
Zustand in Zustand Zno (in der Zeichnung, "Zincorrect") und füge dem Stack "\" und "(" hinzu.
Im Zustand Zno:
Ist gelesenes Symbol "(" unter der Bedingung, dass das oberste Element des Stacks "(" ist, dann bleibe im "Zno", füge aber dem Stack "(", "(" hinzu.
Ist jedoch gelesenes Symbol ")", unter der Bedingung, dass das oberste Element des Stacks "(" ist, dann lösche das Element und bleibe im Zno.
Wenn das Ende der Eingabe erreicht wurden ist, wechsle zu "Zyes", unter der Bedingung, dass der Stack wieder im Bottom ist.
Falls dann ein ")" folgt, Zend wechseln, falls "(", dann von vorne.
Ist das so formal korrekt dargestellt?
Lieben Dank!
ich wollte mal aus Spaß einen Kellerautomaten_ entwerfen, der einen Klammerausdruck verifiziert.
Sigma ist logischerweise {"(",")"}, Kelleralphabet {"/", "(", ")"}, Zustände {"Zin", "Zno", "Zyes", "Zend"}, # = "/", q0 = "Zin", F {"Zyes}, delta = Zustände x (Sigma vereinigt mit epsilon) x Kelleralphabet
mit f(eingabeZeichen, momentanerZustand) und g(stack.pop), wobei eben f und g benutzerdefinierte Funktionen sind.
Die Zeichnung dazu:
Ist das so korrekt?
Erklärung:
Automat befindet sich im Zustand Zin, wird ein "(" gelesen unter der Bedingung, dass das oberste Element des Stacks "\" (q0) ist, dann wechsle
Zustand in Zustand Zno (in der Zeichnung, "Zincorrect") und füge dem Stack "\" und "(" hinzu.
Im Zustand Zno:
Ist gelesenes Symbol "(" unter der Bedingung, dass das oberste Element des Stacks "(" ist, dann bleibe im "Zno", füge aber dem Stack "(", "(" hinzu.
Ist jedoch gelesenes Symbol ")", unter der Bedingung, dass das oberste Element des Stacks "(" ist, dann lösche das Element und bleibe im Zno.
Wenn das Ende der Eingabe erreicht wurden ist, wechsle zu "Zyes", unter der Bedingung, dass der Stack wieder im Bottom ist.
Falls dann ein ")" folgt, Zend wechseln, falls "(", dann von vorne.
Ist das so formal korrekt dargestellt?
Lieben Dank!
Und Gott alleine weiß alles am allerbesten und besser.