Uneindeutigkeit Kellerautomat

Question

Muss der Automat nicht so konzipiert sein, dass es nur die vorgegebene Sprache erkennt und sonst keine andere? Bei Uneindeutigkeit könnte man ja sonst beliebig viele Überführungsfunktionen definieren, die sogar eine andere Sprache akzeptieren würde oder gibt es keine solche Restriktion bei den Kellerautomaten?

Ich habe eine andere Lösung für den Automaten, die aber aufgrund falscher Annahmen durch meine Frage oben falsch sein könnte. Würde diese Funktion gelten oder ist nur die der Musterlösung richtig?

Überführungsfunktion:

(s0, λ, k0) -> (sE, k0)
(s0, a, k0) -> (s0, ak0)
(s0, c, k0) -> (s1, ck0)
(s0, a, a) -> (s0, aa)
(s1, c, c) -> (s2, λ)
(s2, c, k0) -> (s2, λ)
(s0, b, a) -> (s2, λ)
(s1, b, a) -> (s2, λ)
(s2, a, a) -> (s2, λ)
(s2, λ, k0) -> (sE, k0)

Gruß Alex

Answer 1

Hallo,

du hast schon Recht: Jedes Wort, was erzeugt werden kann, ist automatisch Teil der Sprache. Das heißt auch bei ndet KA muss man schauen, dass man nicht zu viele Wörter erkennen kann. Bei der uneindeutigkeit kann es nur zu Sackgassenzuständen kommen, das ist aber kein Problem, solange ich immer einen Weg für jedes Wort meiner Sprache finde.

Bei deiner Überführungsfunktion stimmen leider einige Übergänge nicht bzw. fehlen. Drei Beispiele:

1) Das einzige Wort, das nur aus c's besteht, ist bei dir das Wort cc. Jedoch sollen alle Wörter c^(2r) darstellbar sein.

2) Wenn ich a's am Anfang schreibe, z.B. aaaa, dann kann ich danach nur mit einem b weiter machen und kann kein c schreiben.

3) Der Übergang (s2, c, k0) -> (s2, λ) macht keinen Sinn, du kannst k0 nicht aus dem Keller löschen.

Schau dir das am Besten nochmal an.

Gruß,

Adam (Tutor)

 

Comments

Danke dir Adam,
ja war schon spät wo ich das gemacht habe, habs dann selbst auch gemerkt :)

Wie genau wird es denn dann gefordert? Ich habe nur bei ndet-KA das Problem einzuschätzen, ab wann es "too much" ist. Da man ja potentiell sehr viele Sackgassen Zustände erzeugen kann bewusst oder unbewusst und auch viel mehr Wörter akzeptiert werden als man vielleicht möchte. D.h. allgemein der Regel folgen, dass man das alles ruhig darf, solange jedes Wort der Sprache erkannt wird stimmts?

Durch intelligente Ausnutzung von Zustandswechseln, kann man ja die Akzeptanz von Wörtern durch einen KA gut einschränken, dies is bei ndet nicht unbedingt gefordert, d.h. den ndet-KA so restriktiv wie möglich zu gestalten?

Gruß

---

Hallo,

die Erklärung von Adam finde ich sehr passend:

"du hast schon Recht: Jedes Wort, was erzeugt werden kann, ist automatisch Teil der Sprache. Das heißt auch bei ndet KA muss man schauen, dass man nicht zu viele Wörter erkennen kann. Bei der uneindeutigkeit kann es nur zu Sackgassenzuständen kommen, das ist aber kein Problem, solange ich immer einen Weg für jedes Wort meiner Sprache finde. "

Das mit der Intelligenten Ausnutzung von Zustandswechseln ist auch sehr gut. So wie du dein Vorgehen beschreibst, bist du denke ich auf der sicheren Seite.

 

 Grüße Jördis ( Tutorin )

---

Deine Lösung ist leider falsch. Schau Dir mal das Testwort aaccba an. (s0,aaccba,k0)-->(s0,accba,ak0)-->(s0,ccba,aak0)--> ??

Nun ist kein Zustand mehr definiert. Es gibt kein Zustand mit (s0,c,a)-->...