Reguläre Sprachen
Die regulären - also Typ 3-Sprachen - werden in diesem Abschnitt näher untersucht.
Wie bereits gesehen werden reguläre Sprachen durch reguläre Grammatiken gebildet.
In diesem Abschnitt sollen Automaten eingeführt werden, die reguläre Sprachen akzeptieren, es wird eine weitere Beschreibung für reguläre Ausdrücke vorgestellt und Zusammenhänge aufgezeigt.
Endliche Automaten
Veranschaulicht werden endliche Automaten durch einen Zustandsgraphen. Die Zustände werden durch Kreise gekennzeichnet. Dabei haben der Startzustand und die Endzustände besondere Markierungen:
Startzustand durch hineingehenden Pfeil
Endzustand durch doppleten Kreis
Zustandsübergang
Beispiel: Der DEA akzeptiert alle Wörter auf dem Alphabet {0;1}, die auf "00" enden
In diesem Bild können Sie ganz leicht die Zustände, das Alphabet, den Startzustand und die Endzustände erkennen.
Das ein DEA eine reguläre Grammatik erzeugen kann, soll auch an diesem Beispiel gezeigt werden.