Aufgabe 41 a) Alternative Lösung

Question

Hallo, da die Lsg sehr kurz gefasst ist und ich auf eine andere Lsg gekommen bin wollte ich sicher gehen, dass meine Lsg auch "richtig" ist:

Delta:

(S0, lambda , ko) → (Se, k0)

(S0, a , ko) → (S1, ak0)

(S1, a , ko) → (S1, ak0)

(S1, a , a) → (S1, lambda)

(S1, b, ko) → (Se, k0)

(S1, b , ko) → (S1, bk0)

(S1, a , b) → (S1, ab)

(S1, b , b) → (S1, lambda)

(S1, lambda , ko) → (Se, k0)

Vielen Dank und Liebe Grüße!

Answer 1

Hey uuiya,

deine Lösung sieht leider nicht richtig aus. 

Erste Sache, die es unbedingt zu vermeiden gilt: Die folgenden zwei Übergange sind uneindeutig - du definierst also zwei Möglichkeiten, was passieren kann, wenn man sich in S1 befindet, b einliest und k0 im Keller steht. Damit könnte ein Automat nicht arbeiten.

(S1, b, ko) → (Se, k0)
(S1, b , ko) → (S1, bk0)

Ansonsten kann ich deiner Idee an mehreren Stellen nicht ganz folgen - kannst du vielleicht erklären, was dein Ansatz war? Schauen wir uns beispielsweise deine Übergänge 2-4 an. Dort modellierst du den Automaten so, dass er beliebig viele a's nacheinander akzeptiert. Per Definition in der Aufgabenstellung soll er aber eben nur die Kombination a²b enthalten, und zwar n-mal. Du willst also immer genau 2 a's, dann ein b. Dann ggf. nochmal von vorn. 

Vielleicht hilft das schon, um deinen Fehler zu erkennen, aber stell gerne nochmal eine Rückfrage, wenn etwas unklar ist.

Beste Grüße,

Martin (Tutor)

Comments

Hey Martin,
erstmal vielen Dank für die Antwort und für die Tipps!

Also ehrlich gesagt kann ich dir auch nicht mehr den Ansatz verraten:D ich sehe jetzt bloß auch, dass der KA von mir auf jeden Fall falsch ist.

Ich hab mich grade nochmal hingesetzt und nochmal romprobiert:
Mein Ansatz ist folgender:

1) Ich hab das leer Wort enthalten -> ich kann ohne Eingabe in den Endzustand

2) Als erstes kann ich nur ein a lesen, ich schreibe es in den Keller Wechsel den Zustand in s1.

3) Lese in s1 ein a ein und hab im Keller oben ein a stehen. "Lösche das eine a  mit dem anderen a"(=lambda). Wechsel den Zustand in s2.

4) Dort kann ich ja nur noch ein b einlesen. Dieses lese ich ein schreibe aber nichts in den Keller. (das darf ich ja oder?)
Wechsel den Zustand in s0. (Darf ich das auch, oder??)

So kann es jetzt sein, dass ich keine Eingabe mehr habe -> Endzustand, oder eben wieder "von vorne" anfange.

Konkret:

(S0, lambda , ko) → (Se, k0)

(S0, a , ko) → (S1, ak0)

(S1, a , a) → (S2, lambda)

(S2, b , ko) → (S0, ko)

Wie siehts damit aus?:D

Vielen Dank und Liebe Grüße!

---

Hey,
das sieht für mich soweit schlüssig aus, müsste auch funktionieren.
Beachte aber unbedingt, dass in dieser Aufgabe ein Spezialfall vorliegt! Hier ist ausnahmsweise nicht explizit ein deterministischer(!) KA gefragt, nur deswegen ist deine Lösung so zulässig. Die Musterlösung im Übrigen ebenso.
Also in der Klausur unbedingt darauf achten, was gefragt ist - sowas kann einfache Punkte kosten :)
Liebe Grüße!

---

Top! Dankeschön :)