Kellerautomaten |
27.02.2012, 10:44 | 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 ... |
||
|
|||
27.02.2012, 12:24 | Auf diesen Beitrag antworten » | ||
Karlito | RE: Kellerautomaten Hallo,
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 |
||
27.02.2012, 12:44 | Auf diesen Beitrag antworten » | ||
earthhero | Ja das habe ich verstanden Dank Dir, Du hattest die Wortmitte angesprochen, wie wird diese denn erkannt?! Die kann ja eigentlich nur erraten werden?! |
||
27.02.2012, 13:52 | 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 |
||
Anzeige | |||
|
|||
27.02.2012, 14:18 | 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!? |
||
27.02.2012, 18:04 | 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 |
||
02.03.2012, 22:24 | 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 |
||
03.03.2012, 17:36 | 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 |
||
05.03.2012, 15:37 | Auf diesen Beitrag antworten » | ||
earthhero | Ok dann bin ihc mal gespannt ob wir beiden das gleiche meinen Dank Dir schonmal |
||
06.03.2012, 09:11 | 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 |
||
06.03.2012, 15:44 | Auf diesen Beitrag antworten » | ||
earthhero | Das habe ich selber erfunden wie würde das denn bei dir aussehen |
||
12.03.2012, 13:16 | Auf diesen Beitrag antworten » | ||
Karlito | Hi, eher so wie auf Wikipedia. Also sowas wie: Wobei A_0 das Kellerstartsymbol ist. VG, Karlito |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
Die Neuesten » |