Reguläre Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 22:37 Di 05.02.2013 | | Autor: | starki |
| Aufgabe | Gegeben Sei ein NFA A und ein DFA B über einem Alphabet [mm] \Sigma. [/mm] Beschreibe einen möglichst effizienten Algorithmus,
(i) um zu überprüfen, ob L(A) = [mm] \emptyset
[/mm]
(ii) um zu überprüfen, ob L(B) = [mm] \Sigma [/mm] * |
Also meine Lösung sieht so aus:
i) Ein nichtdeterministisch endlicher Automat hat dann eine leere Menge, wenn es keinen Pfad vom Startknoten zu einem Endknoten gibt.
Wir bauen einen Baum, bei dem der Wurzel der Startknoten ist und jedes Kind der Nachfolgezustand ist bei egal welcher Eingabe. Wichtig ist beim Aufbau des Baumes: Sollte ein Blatt ein Zustand sein, der schon als innerer Knoten oder Wurzel auftaucht (in dem Pfad von der Wurzel bis zu dem Blatt), wird dort nicht mehr weiter gebaut. Bei jedem Schritt prüfen wir, ob die nachfolgenden Zustände Endzustände sind. Wird ein Endzustand erreicht, wird die Prozedur abgebrochen und ausgegeben, dass die Sprache nicht leer ist.
Sollte es jedoch kein Abbruch geben, wird irgendwann jeder Zustand besucht sein. Dann kann man sagen, der NFA akzeptiert kein Wort und somit ist die Sprache die leere Menge.
ii) Minimalautomat vom DFA erstellen und mit dem kleinsten Automaten vergleichen, dessen Anfangszustand = Endzustand ist und der in dem Zustand jedes Zeichen liest.
Was haltet ihr von meinen Lösungen? Sind sie korrekt?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:20 Do 07.02.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
