---

Geschrieben von Gisa am 23.09.2007 um 17:46:

  DEA in NEA

Hallo Forum,

ich habe letztens irgendwo eine Verständnisaufgabe gesehen, wo ein DEA in NEA überführt werden sollte.

Wie ist das denn gemeint?
Schließlich könnte ich doch jeden DEA einen Epsilon Übergang verpassen und schon wäre es eigentlich ein NEA, oder?

Grüße
Gisa

---

Geschrieben von Tobias am 23.09.2007 um 18:27:

 

Jeder DEA ist auch ein NEA, da brauchst du garkeine Epsilontransitionen einfügen.

Vielleicht ist es ein Fehler und es ist die andere Richtung gemeint: NEA -> DEA. (Stichwort: Potenzmengenkonstruktion)

---

Geschrieben von Gisa am 23.09.2007 um 20:54:

 

Nein die Potenzmk. ist es nicht gewesen. Das war eher so eine Fangfrage/Verständnisfrage.
Wie ist jeder DEA ein NEA?

NEA ist aquivalent zu DEA. GIbt es NEA en nur wegen der Leichtigkeit und DEA en wegen der besseren Art der Implementierung?

Grüße
Gisa

---

Geschrieben von Tobias am 23.09.2007 um 21:46:

 

Anders als z.B. bei den Kellerautomaten gibt es zu jedem NEA einen DEA, der dieselbe Sprache erkennt.

Also: Die Sprachklasse der Sprachen, die von NEAs erkannt werden ist identisch mit der Sprachklasse von Sprachen, die von DEAs erkannt werden (das sind die Regulären Sprachen).

---

Geschrieben von Gisa am 26.09.2007 um 14:18:

 

Alles klar Danke Tobias.
--
Anderes Thema.

Wenn ich aus einer (regulären) Grammatik der Form:
S ->aB|bA
A ->a|aS
B -> b|bS

ein DEA erstellen möchte, müsste ich irgendetwas wichtiges beachten?
Wenn kein DEA konstruierbar wäre, so könnte man ein NEA und dann über die Potenzmengenkonstruktion einen DEA erstellen?

Sind solche regulären Grammatiken wie oben üblich für Endliche Automaten?

Danke und Grüße
Gisa

---

Geschrieben von Tobias am 26.09.2007 um 22:43:

 

Mit DEAs oder NEAs beschreibt man reguläre Sprachen. Mit kontextfreien Grammatiken beschreibt man kontextfreie Sprachen. Zu jeder kontextfreien Sprache existiert ein nichtdeterministischer Kellerautomat. Zu manchen auch ein deterministischer Kellerautomat.