Reguläre Ausdrücke und der Satz von Kleene
Lesen anpassen
Nach dieser Lektion kannst du
die Sprache eines regulären Ausdrucks schrittweise aus seinen Teilen bestimmen,
leere Sprache, leeres Wort und Wiederholung sicher unterscheiden,
die Thompson-Konstruktion und die Rückrichtung durch Zustandselimination erklären,
Ausdrücke an Gegenbeispielen prüfen und theoretische Ausdrücke von erweiterten Suchmustern unterscheiden.
Vorausgesetzt: Grammatiken und die Chomsky-Hierarchie, Deterministische endliche Automaten (DEA), Nichtdeterministische Automaten und die Potenzmengenkonstruktion
Ein Scanner soll in einem Programm Bezeichner, Zahlen und Satzzeichen finden. Für die Sprache aller Binärwörter, die auf 01 enden, könnte man einen Automaten zeichnen. Oft lässt sich die gleiche Bedingung kürzer als Bauplan angeben: erst beliebig viele Nullen und Einsen, dann eine Null und eine Eins.
Reguläre Ausdrücke machen solche Baupläne präzise. Ihre drei Grundideen sind Auswahl, Hintereinandersetzen und Wiederholung. Dass diese Beschreibung genau so mächtig ist wie ein endlicher Automat, ist der Satz von Kleene. Er verbindet eine kompakte Schreibweise mit einem ausführbaren Erkennungsverfahren.
Die drei Sprachoperationen
Für Sprachen A und B ist die Vereinigung: Ein Wort gehört dazu, wenn es in mindestens einer der beiden Sprachen liegt. Das Produkt oder die Konkatenation setzt ein Wort aus A vor eines aus B. Dabei ist die Zerlegung nicht unbedingt eindeutig.
Setze und . Der Kleene-Stern erlaubt endlich viele Wiederholungen einschließlich null Wiederholungen. Null Wiederholungen ergeben ε, auch wenn A die leere Sprache ist.
Regulärer Ausdruck und seine Bedeutung
Über einem festen Alphabet Σ sind , ε und jedes Zeichen reguläre Ausdrücke. Sind R und T regulär, dann auch die Auswahl , die Verkettung RT und die Wiederholung . Jeder reguläre Ausdruck entsteht nach endlich vielen solchen Schritten.
Seine Bedeutung ist eine Sprache . Es gilt , und . Auswahl bedeutet Vereinigung, Verkettung bedeutet Sprachprodukt und der Stern bedeutet Kleene-Abschluss. Wir prüfen hier immer das ganze Wort. Der Stern bindet stärker als Verkettung, diese stärker als |. Klammern ändern die Gruppierung.
Klammern entscheiden über die Sprache
Klammern entscheiden über die Sprache
beschreibt entweder das einzelne Wort a oder ein b mit null oder mehr c. Dazu gehören a, b, bc und bcc, aber nicht ac. Der Ausdruck erlaubt dagegen a oder b gefolgt von beliebig vielen c; nun gehört auch ac dazu.
Die Sprache von enthält ε, ab, abab und so weiter. Bei entstehen erst beliebig viele a und dann beliebig viele b. Das erlaubt aab, aber nicht abab. Die Schreibweisen sehen ähnlich aus, beschreiben jedoch unterschiedliche Anordnungen und Abhängigkeiten.
Welche Sprache beschreibt ?
Endung und verbotene Nachbarschaft
Endung und verbotene Nachbarschaft
Für Binärwörter mit Endung 01 lautet ein Ausdruck . Der Sternteil darf leer sein, sodass bereits 01 dazugehört. Ein beliebiger anderer Anfang ist erlaubt; das ganze Wort muss trotzdem mit 01 enden.
Binärwörter ohne 11 beschreibt . Jede Eins, auf die noch etwas folgt, wird mit ihrer nächsten Null als Block 10 gelesen. Eine letzte Eins darf allein im Schlussstück stehen. Umgekehrt erzeugen die Blöcke 0 und 10 auch an ihren Grenzen kein 11. Damit sind beide Richtungen der behaupteten Sprachbeschreibung begründet. Für 10101 ist eine Zerlegung .
Der Pfeil von links zeigt den Start. Ein Doppelkreis ist ein Zustand, in dem ein Wort angenommen wird. Der hervorgehobene Zustand ist gerade aktiv.
- 1
- 0
- 1
- 0
- 1
Start. Der Automat steht in q0. Drücke „Schritt“, um das erste Zeichen zu lesen.
Probier es aus
Satz von Kleene
Eine Sprache lässt sich genau dann durch einen regulären Ausdruck beschreiben, wenn ein endlicher Automat sie erkennt. Damit sind reguläre Ausdrücke, ε-Nichtdeterministen, Nichtdeterministen und deterministische endliche Automaten gleich mächtig. „Gleich mächtig“ bedeutet gleiche Sprachklasse, nicht gleich große Darstellungen.
Die Hinrichtung wird durch strukturellen Aufbau eines ε-NFA bewiesen: Für die Grundausdrücke gibt es kleine Automaten; Auswahl, Verkettung und Stern werden mit ε-Kanten zusammengesetzt. Die Rückrichtung beseitigt Zustände eines Automaten und ersetzt die möglichen Wege durch Ausdrücke. Beide Verfahren sind endlich und erhalten die angenommene Sprache. Die nächsten beiden Abschnitte führen die entscheidenden Erhaltungsschritte aus.
Vom Ausdruck zum ε-NFA: Thompson-Konstruktion
Vom Ausdruck zum ε-NFA: Thompson-Konstruktion
Ein ε-NFA darf eine ε-Kante ohne Eingabezeichen durchlaufen. Wir bauen für jeden Teilausdruck einen Ausschnitt mit eigenem Eingang und Ausgang. Nur der Ausgang des gesamten Ausschnitts ist am Ende akzeptierend. Die Ausschnitte für verschiedene Teile erhalten zunächst verschiedene Zustandsnamen.
Ein Zeichen a erhält eine a-Kante vom Eingang zum Ausgang. Für ε genügt eine ε-Kante. Für die leere Sprache gibt es keinen Weg zwischen beiden.
Verallgemeinerter Automat und Zustandselimination
Für die Rückrichtung beschriften wir Kanten mit regulären Ausdrücken statt nur mit einzelnen Zeichen. Mehrere Kanten zwischen zwei Zuständen werden durch | zusammengefasst, eine fehlende Kante bedeutet . Ergänze einen neuen Startzustand mit ε-Kante zum alten Start und einen neuen einzigen Endzustand mit ε-Kanten von den bisherigen akzeptierenden Zuständen. Die neuen äußeren Zustände bleiben erhalten.
Soll ein innerer Zustand q entfernt werden, muss jeder Umweg über q ersetzt werden. Von einem verbleibenden i nach einem verbleibenden j kann man entweder den bisherigen direkten Weg nehmen oder über q gehen, dort beliebig oft kreisen und wieder nach j gehen. Die alten Beschriftungen heißen , , und . Man berechnet alle neuen Beschriftungen aus diesem alten Stand, auch wenn i=j ist.
Einen Zustand entfernen, seine Wege behalten
Der Stern steht nur an der Schleife von q. Die beiden äußeren Kanten werden je einmal durchlaufen. Bei jeder Elimination werden alle Paare verbleibender Zustände nach derselben Regel aktualisiert; die Skizze zeigt ein solches Paar.
Eine konkrete Elimination und ihre Probe
Eine konkrete Elimination und ihre Probe
Es gebe einen direkten Weg i→j mit Beschriftung d, eine Kante i→q mit a, eine Schleife an q mit b und eine Kante q→j mit c. Dann lautet die neue Beschriftung . Sie erlaubt d, ac, abc, abbc und so weiter. Der Weg ac ist wichtig: Er besucht q, ohne dessen Schleife zu durchlaufen.
Die Regel erhält alle gelesenen Wörter, weil jeder Weg über q in Eintritt, Schleifen und Austritt zerfällt; umgekehrt gibt jeder solche Ausdrucksteil einen entsprechenden alten Weg an. Nach endlich vielen Eliminationen bleiben nur neuer Start und neuer Endzustand. Deren Kantenbeschriftung ist ein Ausdruck für die ursprüngliche Automatensprache.
Jedes Suchmuster in einer Programmiersprache ist mathematisch regulär
Jedes Suchmuster in einer Programmiersprache ist mathematisch regulär
Bibliotheken nennen auch erweiterte Muster „Regex“. Daraus wird manchmal geschlossen, dass jedes ihrer Merkmale nur reguläre Sprachen beschreibt oder jeder Suchaufruf ein ganzes Wort prüft.
Zeichenklassen, endliche Wiederholungsgrenzen und optionale Teile lassen sich mit unseren Operationen ausdrücken. Allgemeine Rückreferenzen sind stärker: Sie können einen beliebig langen zuvor erfassten Teil wiederholen und damit Gleichheiten verlangen, die endliche Automaten nicht allgemein prüfen. Zudem suchen viele Bibliotheken standardmäßig nur einen passenden Teilstring. Hier bedeutet Zugehörigkeit immer, dass das vollständige Wort zur beschriebenen Sprache gehört. Syntax und Auswertungsmodus müssen ausdrücklich bekannt sein.
Zusammenfassung
Auswahl steht für Vereinigung, Verkettung für Sprachprodukt, Stern für endlich viele Wiederholungen einschließlich null.
ε ist ein Ausdruck für das leere Wort; der Ausdruck für die leere Sprache ist . Deren Stern enthält ε.
Kleene verbindet reguläre Ausdrücke und endliche Automaten in beide Richtungen.
Thompson setzt kleine ε-NFA entlang des Ausdrucksaufbaus zusammen.
Zustandselimination ersetzt direkte Wege und Umwege über einen entfernten Zustand durch eine Auswahl.
Ein Gegenwort widerlegt Gleichheit; ein vollständiger Automatentest kann sie entscheiden.
Erweiterte Suchbibliotheken und Teilstringsuche dürfen nicht unbesehen mit der theoretischen Definition gleichgesetzt werden.
Übungen
Welcher Ausdruck beschreibt die Sprache mit genau dem Wort a?
Wie viele verschiedene Wörter beschreibt ?
Welcher Ausdruck beschreibt genau alle Binärwörter, die auf 01 enden?
Wie viele Wörter der Länge 4 beschreibt ?
Gib einen regulären Ausdruck für Binärwörter mit genau einer Eins an und begründe beide Richtungen.
Bei einer Zustandselimination sind die alten Beschriftungen i→j gleich d, i→q gleich a, q→q gleich b und q→j gleich c. Gib die neue Beschriftung an und erkläre, warum ac dazugehört.
Zeige mit je einem Gegenwort, dass und verschieden sind und keine der beiden Sprachen die andere enthält.
Warum muss die Thompson-Konstruktion für eine Möglichkeit haben, den Ausschnitt für R ganz zu überspringen? Reicht es, seinen Ausgang nur zurück zu seinem Eingang zu verbinden?