Zusammenhänge
Worum geht es hier?
Du kennst reguläre Grammatiken sowie deterministische und nichtdeterministische endliche Automaten. Zwischen diesen Beschreibungen einer Sprache lässt sich wechseln. In diesem Abschnitt untersuchst du, ob eines dieser Modelle mehr Sprachen beschreiben kann als die anderen und welche Rolle reguläre Ausdrücke dabei spielen.
Welches Modell ist mächtiger?
Eine reguläre Grammatik lässt sich in einen NEA umwandeln. Aus einem DEA lässt sich wiederum eine reguläre Grammatik gewinnen. Bei diesen Umwandlungen bleibt die beschriebene beziehungsweise erkannte Sprache erhalten.
| Ausgangsmodell | Umwandlung | Ergebnis |
|---|---|---|
| DEA | automatisiert umwandelbar in | reguläre Grammatik |
| reguläre Grammatik | automatisiert umwandelbar in | NEA |
Aufgabe 1 - Die Mächtigkeit der Modelle vergleichen
Was bedeuten diese Umwandlungen für die Mengen der Sprachen, die sich mit den Modellen beschreiben lassen? Welches Modell hältst du für das mächtigste? Begründe deine Vermutung. Ein Modell gilt hier als mächtiger, wenn es mehr Sprachen beschreiben beziehungsweise erkennen kann.
Vom NEA zum DEA
Ein NEA kann für dasselbe Eingabezeichen mehrere mögliche Folgezustände haben und ε-Übergänge enthalten. Lässt sich trotzdem ein DEA finden, der genau dieselbe Sprache erkennt?
Aufgabe 2 - Einen NEA in einen DEA umwandeln
- Öffne die Datei NEA_Binaerzahlen.json in FLACI. Wähle im Menü Konvertieren den Eintrag NEA in DEA.
- Untersuche den erzeugten Automaten. Vergleiche seine Zustände, Übergänge und Endzustände mit denen des NEA. Teste beide Automaten mit denselben Wörtern.
- Welche Konsequenzen ergeben sich aus der Umwandlung für die Mächtigkeit von DEA und NEA? Überprüfe damit deine Vermutung aus Aufgabe 1.
Nichtdeterministischer endlicher Automat
Deterministischer endlicher Automat
Die Zustände des DEA fassen mögliche Nichtterminale der zugrunde liegenden Grammatik zusammen, wie auf der vorherigen Seite erläutert. Andere Zustandsnamen und Anordnungen sind möglich. Beide Automaten erkennen die Binärzahlen ohne führende Nullen, einschließlich der Zahl 0.
Du kannst den gezeigten DEA als FLACI-Datei herunterladen.
Zusammenhang zwischen DEA und NEA
Zu jedem nichtdeterministischen endlichen Automaten gibt es einen deterministischen endlichen Automaten, der dieselbe Sprache erkennt. Der DEA lässt sich automatisiert aus dem NEA erzeugen.
Umgekehrt ist jeder DEA auch ein Spezialfall eines NEA. Beide Automatenmodelle erkennen daher genau dieselben Sprachen. Nichtdeterminismus kann die Darstellung eines Automaten vereinfachen, erweitert aber nicht die Menge der erkennbaren Sprachen.
Damit sind DEA, NEA und reguläre Grammatik drei gleichmächtige Möglichkeiten, eine reguläre Sprache zu definieren. Sie lassen sich unter Erhaltung der Sprache ineinander umwandeln, gegebenenfalls über ein anderes dieser Modelle.
NEA und reguläre Ausdrücke
Zu jedem regulären Ausdruck gibt es einen NEA, der die durch den Ausdruck beschriebene Sprache erkennt.
Zu jedem NEA gibt es umgekehrt einen regulären Ausdruck, der genau die von diesem Automaten erkannte Sprache beschreibt.
Auch zwischen NEA und regulärem Ausdruck ist die Umwandlung in beide Richtungen automatisiert möglich. Mehr dazu erfährst du im Exkurs zum Zusammenhang zwischen regulären Ausdrücken und endlichen Automaten.
Vier gleichmächtige Beschreibungen regulärer Sprachen
| Modell | Wie wird die Sprache festgelegt? |
|---|---|
| Reguläre Grammatik | Produktionen erzeugen die Wörter der Sprache. |
| Regulärer Ausdruck | Ein Ausdruck beschreibt die Wörter der Sprache. |
| DEA | Ein deterministischer endlicher Automat erkennt die Wörter der Sprache. |
| NEA | Ein nichtdeterministischer endlicher Automat erkennt die Wörter der Sprache. |
Die folgenden Klassen von Sprachen sind identisch:
- Sprachen, die eine reguläre Grammatik erzeugt,
- Sprachen, die ein regulärer Ausdruck beschreibt,
- Sprachen, die ein DEA erkennt,
- Sprachen, die ein NEA erkennt.
Diese gemeinsame Klasse heißt Klasse der regulären Sprachen.
Du kannst also die für eine Aufgabe passende Darstellung wählen: Die vier Modelle unterscheiden sich in ihrer Darstellung und Handhabung, besitzen aber dieselbe Ausdrucksmächtigkeit.