inf-schule | Reguläre Sprachen und endliche Automaten » Von der regulären Grammatik zum NEA

Von der regulären Grammatik zum NEA

Hier erstmal nur vorgesehene Inhalte abgelegt, noch nicht weiter bearbeitet

Worum geht es hier?

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 | 0C | 1C
B -> 0B | 1B | 0D | 1D
C -> ε
D -> ε

Aufgabe 1 - Einen Automaten aus einer Grammatik erzeugen

Gib die Grammatik in FLACI ein und lasse sie in einen endlichen Automaten umwandeln. Verwende in FLACI EPSILON für das leere Wort.
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 ε.

Ein möglicher Automat zur Grammatik

Der folgende Automat erkennt die von der Grammatik erzeugte Sprache:

NEA mit Startzustand A und Endzustand E. A führt bei 1 nach B und bei 0 oder 1 nach C. B hat eine Schleife mit 0 und 1 sowie Übergänge mit beiden Zeichen nach D. Von C und D führen Epsilon-Übergänge nach E.

Die Zustände A, B, C und D entsprechen den gleichnamigen Nichtterminalen der Grammatik. Der zusätzliche Endzustand E wird über ε-Übergänge von C und D erreicht. Diese Übergänge entsprechen den Produktionen zum leeren Wort.

Nichtdeterministische endliche Automaten

Am Beispiel fallen zwei Besonderheiten auf:

Vom Zustand A aus sind beim Lesen einer 1 zwei verschiedene Folgezustände möglich: C und B. Ebenso kann der Automat von B aus bei 0 oder 1 entweder in B bleiben oder nach D wechseln. Solche Übergänge nennt man nichtdeterministisch.
Von C und D aus kann der Automat nach E wechseln, 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.

Zum Vergleich: Der folgende DEA erkennt dieselbe Sprache der Binärzahlen ohne führende Nullen, einschließlich der Zahl 0. Seine Zustände fassen die jeweils möglichen Nichtterminale der Grammatik zusammen. Nach der ersten 1 sind beispielsweise B und C möglich. Eine Zustandsmenge ist akzeptierend, wenn sie C oder D enthält, da diese das leere Wort erzeugen können. ∅ bedeutet, dass kein Nichtterminal mehr infrage kommt.

DEA mit Startzustand {A}. Mit 0 geht er nach {C}, mit 1 nach {B,C}. Von {C} führen beide Zeichen nach ∅, das bei beiden Zeichen in ∅ bleibt. Von {B,C} führen beide Zeichen nach {B,D}, das bei beiden Zeichen in {B,D} bleibt. {C}, {B,C} und {B,D} sind Endzustände.

Den DEA kannst du als FLACI-Datei herunterladen.

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.

Beispiel: Eingabe `10`

Für den NEA aus dem aufklappbaren Beispiel ergeben sich die folgenden 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

Öffne die Datei NEA_Binaerzahlen.json in FLACI.

Simuliere die Verarbeitung des Wortes 10 und vergleiche die angezeigten Wege mit der Tabelle.
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}:

NEA mit Startzustand q0 und Endzustand q3. Epsilon-Übergänge führen von q0 nach q1, von q1 nach q3 und von q3 nach q0. Von q0 führt a nach q2. q2 besitzt Schleifen für a, b und c, einen Übergang mit b nach q1 und einen Übergang mit c nach q3.

Notiere vier Wörter, die zur Sprache des NEA gehören, und vier Wörter über dem angegebenen Alphabet, die nicht dazugehören.
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.
Beschreibe die Sprache dieses NEA möglichst genau in Worten.