Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

Fragen zur selbstkontrolle im Buch: Frage 2 bei Kapitel 2

+1 Punkt
78 Aufrufe
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.
Gefragt 25, Jul 2017 in Kapitel 2 von Anonym  

Eine Antwort

+1 Punkt
 
Beste Antwort

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

Beantwortet 25, Jul 2017 von urdxp urdxp Tutor(in) (101,740 Punkte)  
ausgewählt 26, Jul 2017 von Marlon Braun
...