DFA reguläre Sprache?
Ist nicht jede Sprache eine reguläre Sprache?
Man kann doch einfach folgenden DFA konstruieren:
Startzustand gleichzeitig akzeptierter Zustand, Übergangsfunktion verweist für jede Eingabe auf den Startzustand. Ist das denn nicht etwas witzlos?
1 Antwort
Das »F« im DFA steht für »finite«, also endlich. Deine Konstruktion funktioniert also nur für endliche Sprachen (die sind tatsächlich alle regulär). Wirklich interessant sind aber nur die unendlichen Sprachen, und die sind freilich nicht alle regulär.
Das F steht für Finite, im Kontext von endlichen Zuständen [...]
Es gibt keine »endlichen Zustände«, nur eine endliche Anzahl an Zuständen. FDA steht für »finite deterministic automaton«, also ein Automat mit endlichen Zuständen und einer deterministischen Übergangsrelation. Mit Sprachen hat das erst mal nichts zu tun, ja.
Hast du ein Beispiel? :D
Das Standard-Beispiel für eine nicht-reguläre Sprache ist L = {a^nb^n | n > 0}, also zuerst n-mal 'a' und dann n-mal (das gleiche n!) 'b'.
Das F steht für Finite, im Kontext von endlichen Zuständen, nicht Sprachen.
Hast du ein Beispiel? :D