| Die letzten 6 Beiträge |
| Tobias |
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. |
| Gisa |
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 |
| Tobias |
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). |
| Gisa |
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 |
| Tobias |
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) |
| Gisa |
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 |
