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.
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 direkt:
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.