s n h m r u
i

Von der regulären Grammatik zum NEA

Wird noch weiter angepasst.

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

  1. Gib die Grammatik in ein und lasse sie in einen endlichen Automaten umwandeln.
  2. 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

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.

An diesem Automaten 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.

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: Verarbeitung des Wortes 10 mit einem NEA

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.

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

  1. Betrachte die Verarbeitung des Wortes 10 im Simulator und vergleiche die angezeigten Wege mit der Tabelle im obigen Beispiel.
  2. 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.

  1. 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 ε oder e eingeben.

    Wörter der Sprache:

    1.
    2.
    3.
    4.

    Wörter, die nicht zur Sprache gehören:

    1.
    2.
    3.
    4.

  2. 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
  3. Beschreibe die Sprache dieses NEA möglichst genau in Worten.

Suche

v
100.130.2.3.2.3 Von der regulären Grammatik zum NEA
Kopieren durch Anklicken

Rückmeldung geben