Kellerautomaten

Neue Frage »

Auf diesen Beitrag antworten »
earthhero 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 ...
 
Auf diesen Beitrag antworten »
Karlito 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
Auf diesen Beitrag antworten »
earthhero

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?!
Auf diesen Beitrag antworten »
Karlito

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
 
Auf diesen Beitrag antworten »
earthhero

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!?
Auf diesen Beitrag antworten »
Karlito

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
Auf diesen Beitrag antworten »
earthhero

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
Auf diesen Beitrag antworten »
Karlito

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
Auf diesen Beitrag antworten »
earthhero

Ok dann bin ihc mal gespannt ob wir beiden das gleiche meinen smile
Dank Dir schonmal smile
Auf diesen Beitrag antworten »
Karlito

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
Auf diesen Beitrag antworten »
earthhero

Das habe ich selber erfunden smile
wie würde das denn bei dir aussehen smile
Auf diesen Beitrag antworten »
Karlito

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
 
Neue Frage »
Antworten »


Verwandte Themen

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