Von der regulären Grammatik zum NEA
Du hast bereits untersucht, wie sich aus einem deterministischen endlichen Automaten eine reguläre Grammatik gewinnen lässt. Jetzt geht es um den umgekehrten Weg: Aus einer regulären Grammatik soll ein Automat entstehen, der genau die von ihr erzeugte Sprache erkennt. Dabei begegnet dir eine neue Form endlicher Automaten.
Von der Grammatik zum Automaten
Wir betrachten die folgende reguläre Grammatik mit dem Startsymbol A und dem Alphabet {0, 1}:
A -> 1B A -> 0C A -> 1C B -> 0B B -> 1B B -> 0D B -> 1D C -> ε D -> ε
Aufgabe 1 - Einen Automaten aus einer Grammatik erzeugen
- Gib die Grammatik in ein und lasse sie in einen endlichen Automaten umwandeln.
- Untersuche das Übergangsdiagramm. Welche Besonderheiten fallen dir im Vergleich zu den bisher betrachteten deterministischen Automaten auf? Achte auf Übergänge mit gleichem Eingabezeichen und auf Übergänge mit
ε.
Nichtdeterministische endliche Automaten

An diesem Automaten fallen zwei Besonderheiten auf:
- Vom Zustand
Aaus sind beim Lesen einer1zwei verschiedene Folgezustände möglich:CundB. Ebenso kann der Automat vonBaus bei0oder1entweder inBbleiben oder nachDwechseln. Solche Übergänge nennt man nichtdeterministisch. - Von
CundDaus kann der Automat nachEwechseln, ohne ein Eingabezeichen zu lesen. Ein solcher Übergang heißt ε-Übergang.
Ein nichtdeterministischer endlicher Automat (NEA) ist ein endlicher Automat, der für einen Zustand und ein Eingabezeichen mehrere mögliche Folgezustände zulässt. Auch ε-Übergänge sind erlaubt. Für ein Eingabezeichen kann es außerdem keinen passenden Übergang geben.
Bei einem deterministischen endlichen Automaten (DEA) ist dagegen für jeden Zustand und jedes Eingabezeichen genau ein Folgezustand festgelegt. ε-Übergänge sind nicht erlaubt.
Spracherkennung mit einem NEA
Bei einem NEA kann es für dasselbe Eingabewort verschiedene Wege durch den Automaten geben. Um die Zugehörigkeit eines Wortes zu prüfen, müssen alle möglichen Wege berücksichtigt werden. ε-Übergänge verbrauchen dabei kein Zeichen.
Ein NEA akzeptiert ein Wort genau dann, wenn es mindestens einen Weg vom Startzustand zu einem Endzustand gibt, auf dem das gesamte Eingabewort gelesen wird. Dabei dürfen auch ε-Übergänge durchlaufen werden, insbesondere nachdem das letzte Eingabezeichen gelesen wurde.
Das Wort wird abgelehnt, wenn kein solcher Weg existiert. Ein einzelner erfolgloser Weg reicht nicht aus, um das Wort abzulehnen.

Für den obige NEA ergeben sich für die Überprüfung des Worte 10 möglicherweise folgende Wege. In Klammern steht jeweils der noch nicht gelesene Teil der Eingabe; ε bedeutet, dass die Eingabe vollständig gelesen wurde.
| Weg | Zustände und verbleibende Eingabe | Ergebnis |
|---|---|---|
| 1 | A (10) → B (0) → B (ε) |
Die Eingabe ist vollständig gelesen, aber B ist kein Endzustand. |
| 2 | A (10) → C (0) → E (0) |
Ein Endzustand ist erreicht, aber die letzte 0 wurde nicht gelesen. Es gibt keinen passenden weiteren Übergang. |
| 3 | A (10) → B (0) → D (ε) → E (ε) |
Die Eingabe ist vollständig gelesen und ein Endzustand erreicht. |
Der dritte Weg ist erfolgreich. Deshalb akzeptiert der NEA das Wort 10, obwohl die beiden anderen Wege nicht erfolgreich sind.
Aufgabe 2 - Wörter mit dem NEA verarbeiten
- Betrachte die Verarbeitung des Wortes
10im Simulator und vergleiche die angezeigten Wege mit der Tabelle im obigen Beispiel. - Probiere verschiedene weitere Wörter aus. Untersuche dabei Wörter, die akzeptiert werden, und Wörter, die abgelehnt werden. Achte darauf, ob ein Endzustand erst durch einen ε-Übergang erreicht wird und ob beim Erreichen eines Endzustands noch Eingabezeichen übrig sind.
Aufgabe 3 - Die Sprache eines NEA untersuchen
Betrachte den folgenden NEA über dem Alphabet {a, b, c}:

- Notiere vier Wörter, die zur Sprache des NEA gehören, und vier Wörter über dem angegebenen Alphabet, die nicht dazugehören. Für das leere Wort kannst du
εodereeingeben. - Finde nach Möglichkeit für jedes Wort mehrere Wege durch den Automaten. Halte fest, ob das Wort auf dem jeweiligen Weg vollständig gelesen wird und ob ein Endzustand erreicht wird.
NEA im sprachen-automaten-Tool
- Beschreibe die Sprache dieses NEA möglichst genau in Worten.