Kellerautomat, verstehe Musterlösung nicht

Neue Frage »

Auf diesen Beitrag antworten »
coooo Kellerautomat, verstehe Musterlösung nicht

Hallo,

ich lerne gerade für eine sehr wichtige Klausur und verstehe die Musterlösung für eine Aufgabe zu Kellerautomaten nicht.

Die Aufgabenstellung lautet: Die Anzahl von a und b soll gleich der Anzahl c und d sein. Außerdem sollen die Elemente in geordernter Reihenfolge (abcd) sein.

Angenommen, es kommt der String abcd, welcher aktzeptiert werden soll. So steht am Anfgang ein Füllzeichen im Keller #, oder ist er ganz leer? Also bräuchten wir meiner Meinung nach den Zustand a,#,X , wobei X als Symbol steht, dass ein a oder b eingelesen wurde.

In der Musterlösung steht lediglich a, lambda, X. Also ist Füllzeichen = leer?

Außerdem legen wir ein X für ein eingelesenes A in den Keller. Wenn nun anschließend ein B kommt, müsste es einen Zustand "B,x,... " geben. Den gibt es aber irgendwie nicht, kann mir das jemand erklären?

Siehe Anhang. Danke Augenzwinkern
 
Auf diesen Beitrag antworten »
coooo

Außerdem verstehe ich hier bei diesem Beispiel den reflexiven Pfeil im Finalzustand nicht.

B,Z,e, wieso gibt es das doppelt? Auf dem Pfeil von P zu q und dann nochmal von q zu q? Kann mir jemand das erklären?

Und wieso gibt es keinen Zustand falls ein a kommt, und ein Z auf dem stack steht?

also a,Z,ZZ?
Auf diesen Beitrag antworten »
Karlito RE: Kellerautomat, verstehe Musterlösung nicht

Hallo coooo,

ich finde die Lösung auch ein wenig seltsam.

Zitat:
Original von coooo
In der Musterlösung steht lediglich a, lambda, X. Also ist Füllzeichen = leer?


Eigentlich nicht. Denn am Ende wird ein Z vom Stack gelesen um den Finalzustand zu erreichen. Diese lambda-Übergänge zwischendrin finde ich auch ein wenig ungewöhnlich.

Zitat:
Original von coooo
Außerdem legen wir ein X für ein eingelesenes A in den Keller. Wenn nun anschließend ein B kommt, müsste es einen Zustand "B,x,... " geben. Den gibt es aber irgendwie nicht, kann mir das jemand erklären?


Ich denke, dass hier gemeint ist, dass immer ein x auf den Stack gelegt wird, egal ob a oder b gelesen wird. Ich interpretiere [latex]a ,\lambda ; x[/latex] so, dass ein a gelesen wird und egal was bisher auf dem Stack liegt, ein x darauf getan wird.

[latex]\lambda ,\lambda ; \lambda[/latex] ist hingegen so eine Art [latex]\lambda[/latex]- bzw. [latex]\varepsilon[/latex]-Übergang wie bei Automaten und [latex]\lambda ,Z ; \lambda[/latex] soll heißen, dass die Eingabe leer sein muss, das Kelleranfangssymbol gelsen wird und gelöscht wird.

Allgemein finde ich die Notation unschön, weil [latex]\lambda[/latex] einmal für eine leere Eingabe steht und einmal einfach nichts gemacht wird. Ist die Lösung von einem Kommilitonen oder vom Lehrstuhl?

Bei der zweiten Lösung denke ich, dass hier eine alternative Definition des Kellerautomaten zum Einsatz kommt. Dabei ist es so, dass es eigentlich keine Finalzustände gibt (s. Wikipedia). Eine Eingabe wird dann akzeptiert, wenn am Ende der Eingabe der Keller leer ist.

Zitat:
Original von coooo
B,Z,e, wieso gibt es das doppelt? Auf dem Pfeil von P zu q und dann nochmal von q zu q? Kann mir jemand das erklären?


Weil es ja eigentlich eine Eingabe geben muss, bei der in den anderen Zustand gewechselt wird. In der anderen Lösung wurde das einfach mit einer Art [latex]\varepsilon[/latex]-Übergang gelöst. Den habe ich aber so noch nie gesehen (bin aber auch nicht in der theoretischen Inf. zuhause...).

Bei der zweiten Zeichnung wird das Kellerstartsymbol also offensichtlich einfach weg gelassen.

Ich kenne die Notation auch so, dass man, wenn man den Keller befüllt ein Tupel der Form (a, #, #Z) bzw.

Gruß,

Karlito
Auf diesen Beitrag antworten »
coooo

Hallo Karlito


[latex]a ,\lambda ; x[/latex]

Das heißt laut Definition: ein a wird vom Band gelesen, oberstes Zeichen aufm Stack ist ein Lambda, x wird auf den Stack gelegt.

Somit gilt diese Regel nicht, falls wir vorher ein X auf den Stack gelegt haben, da der in der Mitte ja ein Lambda (leer) vorausgesetzt wird : [latex]a ,\lambda ; x[/latex]
 
Auf diesen Beitrag antworten »
Karlito

Dann ist die Lösung aus meiner Sicht falsch, da kein Wort akzeptiert wird.

Man käme ausschließlich mit dem leeren Wort bis zu [latex]q_3[/latex] und von dort aus aber nie zu [latex]q_4[/latex], da sich auf dem Stack ein Z befinden müsste, was da nie abgelegt wurde.

Gruß,

Karlito
Auf diesen Beitrag antworten »
coooo

Doch, ganz am Anfang, falls zB ein a eingelesen wurde.

a, Lambda, X (<--- wird auf stack gelegt)
Auf diesen Beitrag antworten »
Karlito

Aber Z wird nicht auf den Stack gelegt und damit ist [latex]q_4[/latex] nicht erreichbar.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »