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!
 

 

Verständnis

+1 Punkt
90 Aufrufe

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

 

 

 

 

 

 

 

Gefragt 2, Feb 2016 in HU-2-3 von uqdrx uqdrx Eins-Komma-Null-Anwärter(in) (4,290 Punkte)  

Eine Antwort

+1 Punkt
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)
Beantwortet 3, Feb 2016 von ufdzo ufdzo Tutor(in) (102,580 Punkte)  
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).
...