DEA in NEA |
| 23.09.2007, 17:46 | Auf diesen Beitrag antworten » |
| 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 |
|
|
|
| 23.09.2007, 18:27 | Auf diesen Beitrag antworten » |
| 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) |
| 23.09.2007, 20:54 | Auf diesen Beitrag antworten » |
| 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 |
| 23.09.2007, 21:46 | Auf diesen Beitrag antworten » |
| 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). |
| Anzeige | |
|
|
|
| 26.09.2007, 14:18 | Auf diesen Beitrag antworten » |
| 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 |
| 26.09.2007, 22:43 | Auf diesen Beitrag antworten » |
| 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. |
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
