 DEA in NEA |
Gisa 
Mitglied
Dabei seit: 06.02.2007
Beiträge: 47
Herkunft: DE
 |
|
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
__________________
"Imagination ist more than Knowledge"
|
|
23.09.2007 17:46 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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)
|
|
|
23.09.2007 18:27 |
|
|
Gisa
Mitglied
Dabei seit: 06.02.2007
Beiträge: 47
Herkunft: DE
|
|
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
__________________
"Imagination ist more than Knowledge"
|
|
|
23.09.2007 20:54 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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).
|
|
|
23.09.2007 21:46 |
|
|
Gisa
Mitglied
Dabei seit: 06.02.2007
Beiträge: 47
Herkunft: DE
|
|
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
__________________
"Imagination ist more than Knowledge"
|
|
|
26.09.2007 14:18 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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.
|
|
|
26.09.2007 22:43 |
|
|
|
