Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Reguläre Ausdrücke und Sprachen
Wie beschreibt man eine ganze (unendliche) Menge von Wörtern mit einer kurzen Formel? Mit einem regulären Ausdruck. Er ist die dritte, kompakteste Beschreibung regulärer Sprachen, neben DFA und NFA. Klausurpflicht in 8/8 Theo-Inf-Modulen, oft als Umwandlung Regex ↔ Automat.
Die Idee in einem Satz
Ein regulärer Ausdruck beschreibt eine reguläre Sprache durch drei Operationen: Hintereinanderhängen (Konkatenation), Auswahl (Alternative) und Wiederholung (Kleene-Stern).
Die induktive Definition
Reguläre Ausdrücke über einem Alphabet Σ sind induktiv definiert:
Basis:
- ∅ beschreibt die leere Sprache (kein Wort).
- ε beschreibt die Sprache {ε} (nur das leere Wort).
- jedes a ∈ Σ beschreibt die Sprache {a}.
Induktion (wenn r und s reguläre Ausdrücke sind):
- r·s (Konkatenation): erst r, dann s.
- r | s (Alternative, oft r + s): r oder s.
- r* (Kleene-Stern): null oder mehr Wiederholungen von r.
Die beschriebene Sprache L(r)
| Ausdruck | beschriebene Sprache |
|---|---|
| a·b | {ab} |
| a | b |
| a* | {ε, a, aa, aaa, ...} |
| (a | b)* |
| (a | b)*ab |
Operator-Präzedenz
Stern (*) bindet am stärksten, dann Konkatenation, dann Alternative (|).
Beispiel: a|b* bedeutet a | (b*), nicht (a|b)*. Klammern setzen, wenn etwas anderes gemeint ist.
Der Satz von Kleene
Eine Sprache ist genau dann regulär, wenn sie durch einen regulären Ausdruck beschrieben werden kann, genau dann, wenn sie von einem endlichen Automaten erkannt wird.
Regulärer Ausdruck, DFA und NFA sind also drei gleichwertige Beschreibungen derselben Sprachklasse. Man kann jede in jede umwandeln.
Von Regex zu NFA: Thompson-Konstruktion
Die Thompson-Konstruktion baut aus einem regulären Ausdruck systematisch einen ε-NFA: für jede Basis und jede Operation (Konkatenation, Alternative, Stern) gibt es ein kleines Automaten-Bauteil, die man zusammensteckt. So zeigt man eine Richtung des Satzes von Kleene.
Theoretische vs. praktische reguläre Ausdrücke
In der Theorie gibt es nur ∅, ε, Symbole, Konkatenation, | und *. Praktische Regex-Bibliotheken (in Programmiersprachen) haben Zusätze wie +, ?, Zeichenklassen [a-z] und Rückwärtsreferenzen. Achtung: Rückwärtsreferenzen machen praktische Regex MÄCHTIGER als reguläre Sprachen, das ist dann keine reine Theorie mehr.
Klausur-Faustregeln
1. 3 Operationen: Konkatenation, Alternative (|), Kleene-Stern (*).
2. Basis: ∅, ε, einzelne Symbole.
3. Präzedenz: * > Konkatenation > |.
4. r* enthält IMMER das leere Wort ε.
5. Satz von Kleene: Regex = DFA = NFA = reguläre Sprachen.
6. (a|b)* = alle Wörter über {a, b}.
Häufige Stolpersteine
1. ε und ∅ verwechseln. ε ist das leere WORT (Sprache {ε}, ein Element). ∅ ist die leere SPRACHE (kein Element).
2. Stern schließt ε aus. Falsch: a* enthält ε (null Wiederholungen). Für „mindestens ein a“ schreibt man a·a* oder a+.
3. Präzedenz ignorieren. ab* heißt a·(b*), also ein a gefolgt von beliebig vielen b, NICHT (ab)*.
4. Regex für mächtiger halten als Automaten. Theoretische reguläre Ausdrücke sind exakt gleich mächtig wie DFAs/NFAs.
5. Praktische Regex-Features mit Theorie mischen. Rückwärtsreferenzen (\1) gehen über reguläre Sprachen hinaus, sind also nicht „regulär“ im theoretischen Sinn.
6. aⁿbⁿ mit Regex beschreiben wollen. Geht nicht, aⁿbⁿ ist nicht regulär (kein Regex, kein DFA). Regex kann nicht „zählen und vergleichen“.
Interaktiv verstehen
Reguläre Ausdrücke, interaktiv
Wähle einen regulären Ausdruck und prüfe, welche Test-Wörter er beschreibt (grün = Match, rot = kein Match). Tippe auch ein eigenes Wort aus a und b ein und beobachte live, ob es zur Sprache gehört. Das Operatoren-Panel erklärt Konkatenation, Alternative und Kleene-Stern.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Lies einen Ausdruck wie (a|b)*ab von rechts: „irgendetwas, das auf ab endet“. Beim Stern immer das leere Wort mitdenken. Übe beide Richtungen: Sprache → Regex und Regex → Sprache.
Praxis-Übung
Reguläre Ausdrücke, Praxis-Übung
6 Aufgaben zu Syntax, Sprache und Präzedenz.
Klausurfragen mit Lösungen (6)
- F1.Welche Sprache beschreibt der Kleene-Stern a\*?
Antwort: {ε, a, aa, aaa, ...} (null oder mehr a)
Erklärung: a\* (Kleene-Stern) beschreibt null oder mehr Wiederholungen von a, also {ε, a, aa, aaa, ...}. Wichtig: das leere Wort ε ist immer dabei (null Wiederholungen). Für „mindestens ein a“ schreibt man a·a\* oder a+. Klausur-Grundbegriff.
- F2.Welche drei Operationen bilden reguläre Ausdrücke?
Antwort: Konkatenation, Alternative (|), Kleene-Stern (\*)
Erklärung: Die drei Operationen sind Konkatenation (Hintereinanderhängen), Alternative | (Auswahl) und Kleene-Stern \* (Wiederholung). Plus die Basis ∅, ε und einzelne Symbole. AND/OR/NOT gehören zur booleschen Algebra, Push/Pop zum Kellerautomaten. Klausur-Pflichtwissen.
- F3.Ordne den regulären Ausdruck seiner Sprache zu.
Zuordnungen:
- a|b → {a, b}
- ab → {ab}
- (ab)* → {ε, ab, abab, ...}
- (a|b)* → alle Wörter über {a,b}
Erklärung: a|b = Auswahl {a, b}. ab = Konkatenation {ab}. (ab)\* = Wiederholung von ab, inkl. ε. (a|b)\* = beliebige Folge aus a und b, also alle Wörter über dem Alphabet. Klausur-Pflicht-Zuordnung.
Typ: Zuordnung
- F4.Was bedeutet der Ausdruck ab\* (mit Standard-Präzedenz)?
Antwort: ein a, gefolgt von null oder mehr b
Erklärung: Der Stern bindet stärker als die Konkatenation, also ist ab\* = a·(b\*): ein a, gefolgt von null oder mehr b. Für „ab beliebig oft“ müsste man (ab)\* klammern. Präzedenz: \* > Konkatenation > |. Klausur-Stolperstein.
- F5.ε (das leere Wort) und ∅ (die leere Sprache) bezeichnen dasselbe.
Antwort: Falsch
Erklärung: FALSCH. ε ist das leere WORT, die Sprache {ε} enthält genau ein Element (das leere Wort). ∅ ist die leere SPRACHE, sie enthält KEIN Wort. Der Unterschied: {ε} hat ein Element, ∅ hat null Elemente. Klassischer Klausur-Stolperstein.
Typ: Wahr/Falsch
- F6.Welche Sprache lässt sich NICHT durch einen regulären Ausdruck beschreiben?
Antwort: Wörter der Form aⁿbⁿ (gleich viele a wie b)
Erklärung: aⁿbⁿ ist NICHT regulär: ein regulärer Ausdruck (wie ein DFA) kann nicht beliebig große Zahlen zählen und vergleichen. Die anderen drei Sprachen sind regulär (z.B. ((a|b)(a|b))\* für gerade Länge). Die Nicht-Regularität von aⁿbⁿ beweist man mit dem Pumping-Lemma. Klausur-Grenzfrage.
Klausur-Quiz
Reguläre Ausdrücke, Klausur-Quiz
6 Klausur-Fragen zu Kleene, Thompson und Sprachklassen.
Klausurfragen mit Lösungen (6)
- F1.Was besagt der Satz von Kleene?
Antwort: Reguläre Ausdrücke, endliche Automaten und reguläre Sprachen sind gleichwertig
Erklärung: Der Satz von Kleene: Eine Sprache ist genau dann regulär, wenn sie durch einen regulären Ausdruck beschreibbar ist, genau dann, wenn ein endlicher Automat sie erkennt. Regex, DFA und NFA sind also drei gleichwertige Beschreibungen derselben Sprachklasse. Klausur-Kernsatz.
- F2.Welches Verfahren konstruiert aus einem regulären Ausdruck einen NFA?
Antwort: Thompson-Konstruktion
Erklärung: Die Thompson-Konstruktion baut aus einem regulären Ausdruck systematisch einen ε-NFA, indem sie für jede Operation (Konkatenation, Alternative, Stern) ein kleines Automaten-Bauteil zusammensetzt. Die Potenzmengenkonstruktion geht NFA → DFA, der CYK-Algorithmus gehört zu kontextfreien Grammatiken. Klausur-Verfahren.
- F3.Ordne die Basis dem regulären Ausdruck zu.
Zuordnungen:
- ∅ → leere Sprache (kein Wort)
- ε → Sprache {ε} (nur leeres Wort)
- a → Sprache {a}
- a* → {ε, a, aa, ...}
Erklärung: ∅ = leere Sprache (null Wörter). ε = Sprache mit nur dem leeren Wort (ein Element). a = Sprache mit nur dem Wort a. a\* = null oder mehr a, also {ε, a, aa, ...}. Klausur-Pflicht-Zuordnung der Basisfälle.
Typ: Zuordnung
- F4.Welche Präzedenz haben die Regex-Operatoren (von stark zu schwach)?
Antwort: Stern > Konkatenation > Alternative
Erklärung: Die Präzedenz (Bindungsstärke): Kleene-Stern (\*) am stärksten, dann Konkatenation, dann Alternative (|) am schwächsten. Daher ist a|b\* = a | (b\*) und ab\* = a·(b\*). Klammern überschreiben die Präzedenz. Klausur-Pflichtregel.
- F5.Praktische Regex mit Rückwärtsreferenzen können Sprachen beschreiben, die nicht regulär sind.
Antwort: Wahr
Erklärung: RICHTIG. Rückwärtsreferenzen (z.B. (a+)\1 für „etwas, dann dasselbe nochmal“) gehen über die theoretischen regulären Ausdrücke hinaus und können nicht-reguläre Sprachen beschreiben. Reine theoretische Regex (nur ∅, ε, Symbole, Konkatenation, |, \*) sind dagegen exakt so mächtig wie endliche Automaten. Klausur-Abgrenzung Theorie vs. Praxis.
Typ: Wahr/Falsch
- F6.Wie beschreibt man als regulären Ausdruck alle Wörter über {a,b} mit mindestens einem a?
Antwort: (a|b)*a(a|b)*
Erklärung: (a|b)\*a(a|b)\* erzwingt mindestens ein a in der Mitte, davor und danach beliebige Zeichen. a(a|b)\* wäre zu eng (verlangt, dass das Wort MIT a beginnt). a\* enthält nur a (kein b), und das leere Wort. Klausur-Konstruktionsaufgabe: ein Pflicht-Symbol mit (a|b)\* umrahmen.
