Informatiker Board | Druckvorschau: Kellerautomaten

Geschrieben von earthhero am 27.02.2012 um 10:44:

Kellerautomaten

Hallo zusammen, ich bin mal mit dem Kellerautomat angefangen zu lernen.
Nun habe ich einmal einen nichtdeterministischen Kellerautomaten und einen deterministischen Kellerautomaten kennengelernt.
Deterministischer Kellerautomat muss immer die gleiche Anzahl von der gleichen Eingabe haben, z.B. 000111, sind mehr Einsen vorhanden als Nullen, so ist der Keller früher leer, sind mehr Nullen als Einsen vorhanden befinden sich noch Zeichen im Keller, somit im Nicht-Endzustand. Muss allerdings immer die gleiche Reihenfolge haben.

Nicht deterministischer Kellerautomat eigentlich wie ein deterministischer nur die Reihenfolge kann variieren?! (habe ich das richtig verstanden?) Also egal ob 000111 oder 010101...

Was ist das denn für ein Kellerautomat der Palindrome erkennen kann, so einen gibt es ja auch und wie läuft das ab?! Da hätte ich ja z.B. 001100, wären ja im Grunde mehr Nullen als Einsen aber es wird ja trotzdem akzeptiert?!

Das habe ich noch nicht so ganz verstanden ...

Geschrieben von Karlito am 27.02.2012 um 12:24:

RE: Kellerautomaten

Hallo,

Zitat:

Original von earthhero
Nicht deterministischer Kellerautomat eigentlich wie ein deterministischer nur die Reihenfolge kann variieren?! (habe ich das richtig verstanden?) Also egal ob 000111 oder 010101...

Du kannst es nicht an der Reihenfolge fest machen. Der wesentliche Unterschied zwischen den Automaten ist die Übergangsfunktion. Bei einem det. Automaten gibt es zu jedem Zustand und jeder Eingabe nur genau einen Folgezustand. Bei einem nichtdetermistischen Automaten hingegen gibt kann man mit der selben Eingabe in verschiedene Zustände gelangen. Genau das brauchst du für den Kellerautomaten, der Palindrome erkennen kann.

Ein Kellerautomat baut ja zum vergleichen einen Keller auf und baut ihn beim vergleichen wieder ab. Das Problem an Palindromem ist, dass man nicht anhand der Eingabe sagen kann, wo die Wortmitte ist, also ab wann der Keller wieder abgebaut werden muss (das Wort wird ja nur einmal in eine Richtung gelesen).

Hier kommt dir der Nichtdeterminismus zu Gute, indem an jeder beliebigen Stelle entschieden werden kann, dass die Wortmitte erreicht ist und somit der Keller abgebaut werden kann.

Ich hoffe das macht es deutlich.

VG,

Karlito

Geschrieben von earthhero am 27.02.2012 um 12:44:

Ja das habe ich verstanden smile

Dank Dir, Du hattest die Wortmitte angesprochen, wie wird diese denn erkannt?! Die kann ja eigentlich nur erraten werden?!

Geschrieben von Karlito am 27.02.2012 um 13:52:

Genau, die Wortmitte muss "geraten" werden.

Wichtig ist halt, dass deine Übergangsfunktionen so gewählt sind, dass sie nur Palindrome akzeptieren. Aber wann du von dem Zustand bzw. den Zuständen, indenen du den Keller füllst zum Abbauen übergehst, muss frei sein.

VG,

Karlito

Geschrieben von earthhero am 27.02.2012 um 14:18:

Sprich mit Übergangsfunktion meinst du, dass ich bei der Wahl Wortes darauf achte, das es auch ein Palindrom ist?! z.B. 000111111000?

Was ist sonst noch wichtig oder sollte man beim Kellerautomaten wissen!?

Geschrieben von Karlito am 27.02.2012 um 18:04:

Hallo.

Die Wahl des Wortes sollte nicht entscheidend sein.

Wenn du dir den Aufbau von Kellerautomaten anschaust, dann gibt es Übergangsfunktionen, welche bestimmen, von welchem Zustand du mit welcher Eingabe in welchen Folgezustand gelangst. Und das musst du halt so gestalten, dass ausschließlich Palindrome akzeptiert werden. D.h. dass nach dem Aufbau des Kellers nur noch abgebaut wird und keine anderen Operationen erfolgen.

Versuch doch mal bitte einen Automaten zu konstruieren der Palindrome akzeptiert und gib mit die Übergangsfunktionen an.

VG,

Karlito

Geschrieben von earthhero am 02.03.2012 um 22:24:

Naja gibt ja eigentlich nur zwei Zustände, einmal den z0 und z1
(z0,A)-->a(z0,aA)
(z0,a)-->a(z1,leeres Wort) (halt wenn geraten wurde dass die Mitte erreicht ist, dann löscht er den ersten Buchstaben auf dem Kellerstack)
Meintest Du sowas?!
LG

Geschrieben von Karlito am 03.03.2012 um 17:36:

Ja, meinte ich. Muss mich erst mal selber wieder in die Notation einlesen. Deine versteh ich grad nicht...
Komme aber sicher erst morgen zum lesen...

VG,

Karlito

Geschrieben von earthhero am 05.03.2012 um 15:37:

Ok dann bin ihc mal gespannt ob wir beiden das gleiche meinen smile

Dank Dir schonmal smile

Geschrieben von Karlito am 06.03.2012 um 09:11:

Denke das passt ungefähr... Deine Notation ist etwas seltsam, aber wenn ihr das so definiert habt....

Was irgendwie fehlt ist ein Kellerstartsymbol und der Finalzustand...

VG,

Karlito

Geschrieben von earthhero am 06.03.2012 um 15:44:

Das habe ich selber erfunden smile

wie würde das denn bei dir aussehen smile

Geschrieben von Karlito am 12.03.2012 um 13:16:

Hi,

eher so wie auf Wikipedia.

Also sowas wie:
$[latex]<br /> \delta(z_0,a,A_0)=(z_0,AA_0)<br /> [/latex]$

Wobei A_0 das Kellerstartsymbol ist.

VG,

Karlito