Fragen zur selbstkontrolle im Buch: Frage 2 bei Kapitel 2

Question

Ich hätte eine Frage bezüglich der Fragen zur Selbstkontrolle im Buch , und zwar die zweite Frage : Bei einem endlichen Automaten, der das leere Wort akzeptiert, muss der Startzustand s0 ein Endzustand sein. Bei einem Kellerautomaten aber nicht- warum ?".

Endlich Automaten, können das aktuelle Zustand merken, aus einem Zustand s0 muss für eine Eingabe "lambda" ein Endzustand erreicht werden, das Kellerautomat besitzt hingegen ein kellerspeicher der die Eingabe speichern kann, er kann also eine Reihe von zustände annehmen, und dann in einem endzustand (anders als s0) bei eingabe von lambda, halten und das wort akzeptieren. Oder sind bei Kellerautomaten lambda übergänge erlaubt, was bei endlichen Automaten nicht der Fall ist ?

Es ist mir nicht klar wie ich die Frage beantworten kann.

Es wäre sehr nett , wenn jemand mir helfen könnte.

Answer 1

Hey,

Erstmal zum endlichen Automaten: Hier die Zustandsüberführungsfunktion definert, in welche Folgezustand\Folgezustände ein endlicher Automat nach dem Lesen eines Zeichens wechselt. D.h. - liest das Automat nichts, dann wird es auch nicht wechseln. Deswegen, muss per Definition der Startzustand auch ein Endzustand sein - bei Eingabe das leere Wort wird nichts gelesen, und deswegen wechselt das Automat nicht.

Jetzt zur Kellerautomaten: Wir solten erstmal ganz genau anschauen was ein "lambda" übergang bedeutet. 

Falls δ(s, λ, k) definiert ist, ignoriert KA das Eingabeband und verändert nur Keller und Zustand. 

D.h. ein lambda übergang heißt nicht "wir bekommen die Eingabe lambda - und danach pasiert was" - es heißt "falls mein Keller sich in der passende Zustand befindet, kann ich das Eingabeband ignorieren und ohne das Lesekopf zu bewegen, ein Zustandswechsel durchführen".

Deswegen beim Kellerautomaten kann man ein übergang  δ(s0, λ, k0) → (se,  k0) definieren, was die Möglichkeit bietet direkt in der Endzustand (ohne Eingabe) zu wechseln.

Ich hoffe das hilft.

Viele Grüße,

Kaleb