Informatiker Board | Automatentheorie | Kellerautomat, verstehe Musterlösung nicht

Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Kellerautomat, verstehe Musterlösung nicht

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Kellerautomat, verstehe Musterlösung nicht

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

coooo
Jungspund

Dabei seit: 01.02.2015
Beiträge: 22

Kellerautomat, verstehe Musterlösung nicht

Zitatantwort auf diesen Beitrag erstellen

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

coooo hat dieses Bild (verkleinerte Version) angehängt:

08.04.2015 20:24

Nehmen Sie coooo in Ihre Freundesliste auf

coooo
Jungspund

Dabei seit: 01.02.2015
Beiträge: 22

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?

coooo hat dieses Bild (verkleinerte Version) angehängt:

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von coooo: 08.04.2015 21:09.

08.04.2015 20:58

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

09.04.2015 16:36

Nehmen Sie Karlito in Ihre Freundesliste auf

coooo
Jungspund

Dabei seit: 01.02.2015
Beiträge: 22

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]$

09.04.2015 21:43

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

09.04.2015 21:59

coooo
Jungspund

Dabei seit: 01.02.2015
Beiträge: 22

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

a, Lambda, X (<--- wird auf stack gelegt)

09.04.2015 22:54

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Aber Z wird nicht auf den Stack gelegt und damit ist [latex]q_4[/latex]

nicht erreichbar.

10.04.2015 00:22

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Kellerautomat, verstehe Musterlösung nicht