Verständnis

Question

Guten Abend,

 

leider verstehe ich die folgenden Zeilen nicht bei Tut 2 A7 b)

 

(s0, λ, k0)→ (s4, k0)

Wieso gilt denn hier das ? Weil durch das Sternchen (a,b)* auch für i=j=k=0 wir in einen Endzustand kommen müssen ?

(s1, a, a) →(s3,λ)

Wenn mein j=0 ist, dann springe ich gleich in den Zustand s3. Ist deshalb der KA ndet ?

(s2,λ,k0)→(s4,k0)

Kann mir jemand erklären, was wir hier machen ?

Normalerweise lese ich in Zustand s2 b´s und lösche meine a´s damit. Wenn ich nun keine b´s habe, wieso bin ich dann in einem Endzustand. In meinem Keller befinden sich doch dann immer noch a´s und in einem Endzustand kann ich mich nur befinden, wenn mein Keller leer ist..

 

Beste Grüße

 

 

 

 

 

 

 

Answer 1

Hallo uqdrx,

genau, die Regel $ (s_0, \lambda , k_0) \rightarrow (s_4, k_0 ) $ ist hinzugefügt, dass der Automat auch das leere Wort akzeptiert. Der Kellerautomat wird dadurch aber auch nichtdeterministisch – er kann, falls als nächstes Zeichen ein $ a $ folgt und er sich in Zustand $ s_0 $ befindet "entscheiden", ob er direkt das $ a $ einliest (und die zweite Regel befolgt) oder ein $ \lambda $ "einfügt (und die erste Regel befolgt). Etwas formaler ausgedrückt ergibt sich durch diese "Wahl" ein Konfigurationsbaum, in dem wir alle Möglichkeiten betrachten.

Die Zeile $ (s_1 , a , a) \rightarrow (s_3 , \lambda ) $ sorgt dafür, dass auch Wörter behandelt werden können, die kein $ b $ enhalten. Der Automat macht dies – ähnlich wie die Kellerautomaten, die Palyndrome erkennen – indem er an jeder möglichen Stelle im Wort eine Möglichkeit einräumt, dass gerade die Mitte des Wortes erreicht ist. Deswegen gibt es auch immer eine Konfigurationsfolge, die bei einem Wort mit einer gerade Anzahl an $ a $ in einem Endzustand mit einem leeren Keller endet.

Ich hoffe, ich konnte etwas helfen, wenn nicht, frag' gerne nochmal nach :)

Viele Grüße

Jonas (Tutor)

Comments

Hallo Jonas,

Aber nur wegen dem * gilt (s0,λ,k0)→(s4,k0) oder ? Bei einem + würde diese Zeile entfallen ?

Und was besagt diese Zeile (s2,λ,k0)→(s4,k0)?

Vielen Dank für deine Hilfe !:)

---

Genau, bei einem + wäre das leere Wort nicht mehr Element der Sprache und wir müssten auch im Automaten nicht mehr dafür sorgen, dass das Wort angenommen wird.
Die Zeile $ (s_0 , \lambda , k_0 ) \rightarrow (s_4 , k_0 ) $ sorgt dafür, dass auch Wörter akzeptiert werden können, die die Struktur $ w = a^nb^n, n \in IN $  akzeptiert werden können. Das ist durch den Kommentar in der Lösung angedeutet ($ k = 0 $ heißt gerade, dass es keine $ a $ am Ende des Wortes gibt).