Lektion 2.2

Reguläre Ausdrücke und der Satz von Kleene

50 min Lesezeit
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.

Definition

Die drei Sprachoperationen

Für Sprachen A und B ist A∪BA\cup B die Vereinigung: Ein Wort gehört dazu, wenn es in mindestens einer der beiden Sprachen liegt. Das Produkt oder die Konkatenation AB={uv∣u∈A,v∈B}AB=\{uv\mid u\in A,v\in B\} setzt ein Wort aus A vor eines aus B. Dabei ist die Zerlegung nicht unbedingt eindeutig.

Setze A0={ε}A^0=\{\varepsilon\} und An+1=AnAA^{n+1}=A^nA. Der Kleene-Stern erlaubt endlich viele Wiederholungen einschließlich null Wiederholungen. Null Wiederholungen ergeben ε, auch wenn A die leere Sprache ist.

A∗=⋃n≥0An,A∅=∅,A{ε}=A,∅∗={ε}A^*=\bigcup_{n\ge0}A^n,\qquad A\varnothing=\varnothing,\qquad A\{\varepsilon\}=A,\qquad\varnothing^*=\{\varepsilon\}
Definition

Regulärer Ausdruck und seine Bedeutung

Über einem festen Alphabet Σ sind ∅\varnothing, ε und jedes Zeichen a∈Σa\in\Sigma reguläre Ausdrücke. Sind R und T regulär, dann auch die Auswahl (R∣T)(R\mid T), die Verkettung RT und die Wiederholung R∗R^*. Jeder reguläre Ausdruck entsteht nach endlich vielen solchen Schritten.

Seine Bedeutung ist eine Sprache L(R)L(R). Es gilt L(∅)=∅L(\varnothing)=\varnothing, L(ε)={ε}L(\varepsilon)=\{\varepsilon\} und L(a)={a}L(a)=\{a\}. 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.

Beispiel

Klammern entscheiden über die Sprache

a∣bc∗a\mid bc^* 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 (a∣b)c∗(a\mid b)c^* erlaubt dagegen a oder b gefolgt von beliebig vielen c; nun gehört auch ac dazu.

Die Sprache von (ab)∗(ab)^* enthält ε, ab, abab und so weiter. Bei a∗b∗a^*b^* 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.

Kurz geprüft

Welche Sprache beschreibt ∅∗\varnothing^*?

Beispiel

Endung und verbotene Nachbarschaft

Für Binärwörter mit Endung 01 lautet ein Ausdruck (0∣1)∗01(0\mid1)^*01. 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 (0∣10)∗(ε∣1)(0\mid10)^*(\varepsilon\mid1). 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 10⋅10⋅110\cdot10\cdot1.

Derselbe Bauplan als Automatenlauf
01010, 1q0q1q_tot

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
  2. 1
  3. 0
  4. 1
Im Simulator öffnen

Start. Der Automat steht in q0. Drücke „Schritt“, um das erste Zeichen zu lesen.

Der Automat erkennt dieselbe Sprache wie der Ausdruck ohne 11 und die rechtslineare Grammatik der vorigen Lektion. q0 und q1 sind akzeptierend; q_tot merkt eine bereits gelesene verbotene Nachbarschaft. Ein Lauf erklärt ein Wort, die Sprachbegründung muss alle Wörter erfassen.

Probier es aus

Satz

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.

Schritt für Schritt

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.

  1. 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.

Schritt 1 von 4
Definition

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 ∅\varnothing. 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 RijR_{ij}, RiqR_{iq}, RqqR_{qq} und RqjR_{qj}. Man berechnet alle neuen Beschriftungen aus diesem alten Stand, auch wenn i=j ist.

Rijneu=Rij∣Riq(Rqq)∗RqjR_{ij}^{\mathrm{neu}}=R_{ij}\mid R_{iq}(R_{qq})^*R_{qj}

Einen Zustand entfernen, seine Wege behalten

iqjRijRiqRqjRqq

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.

Beispiel

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 d∣ab∗cd\mid ab^*c. 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.

Häufige Fehler

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.

Richtig ist

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 ∅\varnothing. 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

Aufgabe 1Multiple Choice

Welcher Ausdruck beschreibt die Sprache mit genau dem Wort a?

Aufgabe 2Numerisch

Wie viele verschiedene Wörter beschreibt (a∣b)(a∣b)(a\mid b)(a\mid b)?

Aufgabe 3Multiple Choice

Welcher Ausdruck beschreibt genau alle Binärwörter, die auf 01 enden?

Aufgabe 4Numerisch

Wie viele Wörter der Länge 4 beschreibt (0∣10)∗(ε∣1)(0\mid10)^*(\varepsilon\mid1)?

Aufgabe 5Freitext

Gib einen regulären Ausdruck für Binärwörter mit genau einer Eins an und begründe beide Richtungen.

Aufgabe 6Freitext

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.

Aufgabe 7Freitext

Zeige mit je einem Gegenwort, dass a∗b∗a^*b^* und (ab)∗(ab)^* verschieden sind und keine der beiden Sprachen die andere enthält.

Aufgabe 8Freitext

Warum muss die Thompson-Konstruktion für R∗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?