Reguläre Sprachen - Keller Automaten

Hallo Leute,

Ich soll einen Deterministischen Keller Automaten bestimmen, der die Sprache
L = {a^n b^n | n > 0}
akzeptiert und mit 3 Zuständen auskommt.

Wenn ich die Sprache richtig verstehe, soll dass doch heißen, dass der Buchstabe a n-mal vorkommt und dann Buchstabe b in gleicher Anzahl folgt, wobei n eben eine natürliche Zahl größer 0 ist.

Wie kann man soetwas in 3 Zuständen realisieren? Ein paar Anregungen würde mir schon helfen.

Bashar

In einem Zustand akzeptiert er a's und schmeißt sie auf den Stack, bei b geht er in den nächsten Zustand. Dort akzeptiert er b's und nimmt die a's vom Stack. Ist der Stack leer, geht er in den letzten Zustand, indem die Eingabe am Ende sein muss.
Ich hab zwar keine Ahnung, ob das deiner Definition von Kellerautomat entspricht, aber ungefähr könnte es hinkommen. Die Sprache ist BTW nicht regulär.

Was ist ein keller automat? Gibts dafür auch einen vernünftigen namen?(um jetzt mal die debatte mit den meiner meinung nach schrecklichen übersetungen/eigenkreationen wieder in den vordergrund zu holen).

Bashar

versteher schrieb:

Was ist ein keller automat? Gibts dafür auch einen vernünftigen namen?

push-down automaton. Stackautomat wäre auch logisch, das Wort hab ich aber tatsächlich noch nie gehört.

this-*gt*that

versteher schrieb:

Was ist ein keller automat? Gibts dafür auch einen vernünftigen namen?(um jetzt mal die debatte mit den meiner meinung nach schrecklichen übersetungen/eigenkreationen wieder in den vordergrund zu holen).

Der Kellerautomat wurde von einem Deutschen erfunden. So viel zu der schrecklichen Übersetzung.

Zum Problem:
Du hast Zustände Z = {z0,z1,z2}, ein Bandalphabet Sigma = {a,b}, ein Kelleralphabet T = {a, ENDE} sowie eine Übergangsrelation delta:
Startzustand z0, ENDE steht auf dem Keller
wenn du in z0 ein a liest, schreibst du ein a auf den Keller und bleibst in z0
wenn du ein b in z0 liest und ein a steht auf dem Keller, gehst du in z1 und löschst ein a
wenn du ein b in z1 liest, bleibst du in z1 und löschst ein a
wenn du in z1 fertig mit dem lesen bist und ENDE auf dem Kellersteht, gehst du nach z2.

Bashar

this->that schrieb:

Der Kellerautomat wurde von einem Deutschen erfunden. So viel zu der schrecklichen Übersetzung.

Belege?

Deswegen hab ich auch übersetzung/eigekreation geschrieben. Aber jetzt ist es ja auch noch schön geklärt usw.

http://de.wikipedia.org/wiki/Kellerautomat
Nun hab ichs wirklich verstanden, also das ist das theoretische modell, das auch einem parser zugrunde liegen kann. Nunja abstraktion kann schon wichtig sein, aber manchmal wird das schon sehr theoretisch.

this-*gt*that

Bashar schrieb:

Belege?

http://de.wikipedia.org/wiki/Stapelspeicher

Geschichte
Die Verwendung eines Stapelspeichers zur Übersetzung von Programmiersprachen wurde 1957 von Friedrich Ludwig Bauer und Klaus Samelson unter dem Namen „Kellerprinzip“ patentiert [1] und etwa zur selben Zeit unabhängig vom australischen Philosophen Charles Hamblin entdeckt. Die lange ausgebliebene internationale Anerkennung und Ehrung ihrer Leistung erfolgte erst im Jahre 1988. Friedrich Ludwig Bauer erhielt den legendären Computer Pioneer Award (IEEE) für Computer Stacks (Samelson war inzwischen verstorben).

http://www.lexolino.de/c,technik_informatik_it-glossar_s,stack

Entdeckt wurde der Stapelspeicher 1957 von Klaus Samelson und Friedrich Ludwig Bauer, die es unter dem Namen "Kellerprinzip" patentieren ließen

Bashar

OK akzeptiert, ich hätte genauer nachfragen sollen. Die beiden mögen ja den Kellerautomaten erfunden haben, aber sie haben mit Sicherheit nicht den Kellerspeicher AKA Stack erfunden, oder wie hat man vor 1957 rekursive Prozeduren realisiert? Ich wette man hat dazu vorher auch schon Keller gesagt.

ich hab' mal irgendwo gelesen, dass bei einem 'keller' nur das oberste element sichtbar ist. das darunter sieht man erst, wenn man das oberste entnommen hat usw. bei 'nem stack kann man alle elmente sehen (z.b. welches das dritte von unten ist), aber nur das oberste herunterholen. ob dieses bild richtig ist, weiss ich aber nicht.
aber egal, 'keller' ist für stacks trotzdem ein blödes wort.