Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » Kellerautomaten

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Kellerautomaten

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

earthhero
Jungspund

Dabei seit: 22.02.2012
Beiträge: 15

Kellerautomaten

Zitatantwort auf diesen Beitrag erstellen

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 10:44

Nehmen Sie earthhero in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Karlito: 27.02.2012 12:25.

27.02.2012 12:24

Nehmen Sie Karlito in Ihre Freundesliste auf

earthhero
Jungspund

Dabei seit: 22.02.2012
Beiträge: 15

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?!

27.02.2012 12:44

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

27.02.2012 13:52

earthhero
Jungspund

Dabei seit: 22.02.2012
Beiträge: 15

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!?

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von earthhero: 27.02.2012 14:38.

27.02.2012 14:18

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Karlito: 27.02.2012 18:05.

27.02.2012 18:04

earthhero
Jungspund

Dabei seit: 22.02.2012
Beiträge: 15

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

02.03.2012 22:24

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

03.03.2012 17:36

earthhero
Jungspund

Dabei seit: 22.02.2012
Beiträge: 15

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

Dank Dir schonmal smile

05.03.2012 15:37

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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 09:11

earthhero
Jungspund

Dabei seit: 22.02.2012
Beiträge: 15

Das habe ich selber erfunden smile

wie würde das denn bei dir aussehen smile

06.03.2012 15:44

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Karlito: 12.03.2012 13:17.

12.03.2012 13:16

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Kellerautomaten