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).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
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).
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.
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.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
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.
Ein regulärer Ausdruck beschreibt eine reguläre Sprache durch drei Operationen: Hintereinanderhängen (Konkatenation), Auswahl (Alternative) und Wiederholung (Kleene-Stern).
Reguläre Ausdrücke über einem Alphabet Σ sind induktiv definiert:
Basis:
Induktion (wenn r und s reguläre Ausdrücke sind):
| Ausdruck | beschriebene Sprache |
|---|---|
| a·b | {ab} |
| a | b |
| a* | {ε, a, aa, aaa, ...} |
| (a | b)* |
| (a | b)*ab |
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.
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.
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.
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.
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}.
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“.
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.
6 Aufgaben zu Syntax, Sprache und Präzedenz.
Klausurfragen mit Lösungen (6)
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.
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.
Zuordnungen:
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
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.
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
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.
6 Klausur-Fragen zu Kleene, Thompson und Sprachklassen.
Klausurfragen mit Lösungen (6)
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.
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.
Zuordnungen:
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
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.
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
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.