Theorie - Reguläre Sprachen und endliche Automaten

Zusammenhang zwischen deterministischen Automaten und regulären Sprachen

Die Experimente in den vorangegangenen Abschnitten deuten darauf hin, dass es Zusammenhänge zwischen endlichen Automaten und regulären Sprachen gibt.

Satz (über den Zusammenhang zwischen deterministischen endlichen Automaten und regulären Sprachen):
Die Sprache eines deterministischen endlichen Automaten (Akzeptors) ist regulär: Zum deterministischen endlichen Automaten gibt es eine reguläre Grammatik, die dieselbe Sprache erzeugt, die vom Automaten erkannt wird. Man kann diese reguläre Grammatik automatisiert erzeugen.

Dieser Satz kann formal bewiesen werden. Die Idee des Beweises ist recht einfach:

Zunächst werden die Zustände des Automaten mit Nichtterminalsymbolen markiert. Jeder Zustandsübergang kann dann direkt in eine Produktion übertragen werden. So wird der hervorgehobene Zustandsübergang des gezeigten endlichen Automaten in die Produktion S -> 1A übersetzt.

Zustandsübergang

Für jeden Endzustand wird zusätzliche eine Produktion mit dem leeren Wort als rechter Seite ergänzt. Startsymbol ist das Symbol, das zum Startzustand gehört. Im Fall des gezeigten Akzeptors A ergibt sich die Grammatik GA:

S -> 0B
B -> λ
S -> 1A
A -> 0A
A -> 1A
A -> λ

Zusammenhang zwischen regulären Sprachen und deterministischen Automaten

Analog lässt sich eine reguläre Grammatik G in einen endlichen erkennenden Automaten AG übersetzen. Da Grammatiken nicht deterministisch sein müssen, muss auch der resultierende endliche Automat nicht determinstisch sein.

Satz (über den Zusammenhang zwischen regulären Sprachen und nichtdeterministischen endlichen Automaten):
Zu jeder regulären Sprache gibt es einen nichtdeterministischen endlichen Automaten, der diese Sprache erkennt. Der nichtdeterministische endliche Automat kann automatisiert aus einer reguläre Grammatik zur regulären Sprache erzeugt werden.

Mit dem Satz über den Zusammenhang zwischen deterministischen und nichtdeterministischen Automaten folgt jetzt diekt:

Satz (über den Zusammenhang zwischen regulären Sprachen und deterministischen endlichen Automaten):
Zu jeder regulären Sprache gibt es einen deterministischen endlichen Automaten, der diese Sprache erkennt. Der deterministische endliche Automat kann automatisiert aus einer reguläre Grammatik zur regulären Sprache erzeugt werden.

Die regulären Sprachen sind also genau die Sprachen, die von deterministischen erkennenden Automaten erkannt werden.

X

Fehler melden

X

Suche