Kellerautomat: zwei Wörter, die gleich lang aber nicht gleich sind

Wissenschaft Informatik
#1

Hallo, 

ich bin gerade etwas am grübeln, ich suche einen Kellerautomaten, der folgende Sprache erkennt:L = { xy | x,y aus {a,b}*, |x| = |y|, x != y }
Also einen Automaten, der zwei wörter hintereinander, die gleich lang jedoch nicht gleich sind, erkennt.

Kann mir jemand einen Tipp geben? Gerade stehe ich echt auf dem Schlauch.
Zum vergleichen der Länge würde ich x auf den Keller schreiben und beim lesen von y jeweils ein pop durchführen, sodass am Ende der leere Keller stehen würde. Jedoch geht ein vergleich auf diese Art ja nicht, da ich immer nur auf das oberste Element des Kellers zugreifen kann.

Vielen Dank!

#2

Hallo,

ohne jetzt gerade den Beweis im Ärmel zu haben, behaupte ich mal, dass die angegebene Sprache nicht kontextfrei ist.
Die Definition der Sprache impliziert, dass Symbole über einen nicht beschränkten Abstand im Wort korreliert sein können. Das können KFS nicht leisten.
Dann gibt es auch keinen Kellerautomaten, der sie akzeptiert.

Gruß,
KHK

#3

Danke für die Antwort! Jedoch ist in der Aufgabenstellung klar nach einem Kellerautomaten gefragt. Somit sollte die Sprache in CFL liegen.

Jedoch ist kein Diagram oder so gefordert, man soll lediglich die Arbeitsweise des Automaten angeben, der die Sprache erkennt

#4

Danke für die Antwort! Jedoch ist in der Aufgabenstellung klar
nach einem Kellerautomaten gefragt. Somit sollte die Sprache
in CFL liegen.

Wo wurde denn die die Aufgabe gestellt? Schule, Universität, Rätselheft?
Es kann durchaus sein, dass es der tiefere Sinn der Aufgabe ist, die Unlösbarkeit zu erkennen.
Gruß,
KHK

#5

Definitiv nein… Ist eine Uniaufgabe, habe auch mal nachgefragt, soll auf jeden fall lösbar sein.