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

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

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 7 Beiträge

Karlito

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

nicht erreichbar.

coooo

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

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

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

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

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

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?

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

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

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