Es soll zunächst eine Sprache entwickelt werden, die von einem Paritätsprüfer akzeptiert wird mit dem folgenden Zustandsgraph:
Dieser Automat erkennt Wörter, die eine ungerade Anzahl an Einsen haben, zwischen die beliebig viele Nullen eingestreut sind.
Die Menge der Terminalzeichen der zu suchenden Sprache ist T = {0,1}. Der Zustandsgraph des Paritätsprüfers hat zwei Zustände, den Startzustand z0 und den Endzustand z1. Für den Startzustand z0 wird nun der Buchstabe S und für den Endzustand z1 wird A benutzt. Es sei damit N = {S,A} die Menge der Nicht-Terminalzeichen.
Die zugehörige Grammatik lautet :
S à 1A | 0S
A à 0A | 1S | Ø ( Ø entspricht dem leeren Wort )
Eine Grammatik heisst,
wenn alle Produktionen von dieser Form sind:
A à aB oder A à a oder A à Ø
Eine Formale Sprache heisst regulär, wenn sie
eine reguläre Grammatik besitzt.
Die Sprache zum Paritätsprüfer ist demnach
regulär und beinhaltet offenbar genau die vom Paritätsprüfer erkannten Worte.
Umgekehrt lässt sich auch zu jeder regulären Grammatik ein endlicher Automat
angeben, der die von der Grammatik erzeugten Worte erkennt.
Jedem Nicht-Terminalzeichen der Grammatik wird genau ein Zustand des Automaten zugeordnet.
Jeder Produktion entspricht eine Kante im Zustandsgraph. Diese Kante ist dann mit dem
Terminalzeichen der zugehörigen Produktion beschriftet.
Somit gilt der allgemeine Satz :
| Jede von einem endlichen Automaten akzeptierte Sprache ist regulär. Zu jeder regulären Sprache gibt es einen endlichen Automaten, der sie akzeptiert. |
Weitere Beispiele: Akzeptor .....b Akzeptor für (ab)^n
Frage: Gibt es formale Sprachen, die
von keinem endlichen Automaten erkannt werden können?
Es existieren in der Tat solche Grenzen endlicher Automaten