Beispiel zu ndet. KA

Question

Ich hab dazu auch noch folgende Frage:

Angenommen wir haben das Wort aabb und wir sollen prüfen, ob der (ndet.) Kellerautomat (KA) die Sprache a^nb^n erkennt. Wenn ich jetzt folgende zwei Zustandsübergange definiere:

(s0,lambda,k0) -> (se,k0)

(s0,a,k0) -> (s0,ak0)

Könnte es dann sein, dass der KA das Wort aabb gar nicht liest und deswegen den ersten Übergang wählt?

Also im Endeffekt sind das ja nicht genau die gleichen Übergänge, jedoch habe ich schon bei Aufgaben gesehen, dass wenn sowas auftaucht, der KA nicht deterministisch ist.

Answer 1

Hallo ueyfv,

dein vorgeschlagener Automat ist in der Tat nichtdeterministisch, da ein Lambda-Übergang im Startzustand möglich ist. Zu Beginn kann der Automat also theroretisch entweder in s0 bleiben oder in se wechseln.

Bei der Frage, ob der nichtdeterministische Kellerautomat das Wort aabb erkennt, musst Du Dir alle möglichen Übergänge anschauen. Falls eine Folge von Zustandsübergängen existiert, nach der der Kellerautomat nach Abarbeitung des Wortes im Endzustand landet, so ist er auch in der Lage, das Wort zu erkennen. Unabhängig davon, ob er am Anfang auch einen anderen Übergang wählen kann oder nicht.

Viele Grüße

Jannik (Tutor)

Comments

Heißt das also, dass sobald ein Lambda-Übergang existiert, dass der KA nicht deterministisch ist?

---

Falls ein Lambda-Übergang von s0 aus existiert, stimmt Deine Aussage.

Falls ein Lambda-Übergang in einem anderen Zustand existiert, muss man den Automaten genauer untersuchen. In Tut 2 Aufgabe 5 siehst Du z.B. einen deterministischen Kellerautomaten, der einen Lambda-Übergang in s1 besitzt.

---

Ja okay, deinen ersten Fall hatte ich eigentlich auch gemeint.
Besten Dank!