FSK-4VL-07-05-24

• Übersetzung von verschiedenen Formalisten Klausurrelevant [completion:: 2024-07-15]

VL-04a

Summary

Reguläre Ausdrücke

Definition

Ein regulärer Ausdruck über einem Alphabet $\Sigma$ ist definiert durch:

• $\varnothing$ und $ϵ$ sind reguläre Ausdrücke.
• Jedes $a\in \Sigma$ ist ein regulärer Ausdruck.
• Wenn $\alpha$ und $\beta$ reguläre Ausdrücke sind, dann sind auch die Konkatenation $\alpha \beta$, die Auswahl $(\alpha |\beta )$, und die Kleene-Stern Operation $(\alpha {)}^{\ast }$ reguläre Ausdrücke.

Erzeugte Sprache

Die von einem regulären Ausdruck $\alpha$ erzeugte Sprache $L(\alpha )$ wird definiert als:

$$\begin{array}{rl}L(\varnothing )& =\varnothing ,\\ L(ϵ)& =\{ϵ\},\\ L(a)& =\{a\},\text{ fu¨r }a\in \Sigma ,\\ L(\alpha \beta )& =L(\alpha )L(\beta )=\{uv|u\in L(\alpha ),v\in L(\beta )\},\\ L(\alpha |\beta )& =L(\alpha )\cup L(\beta ),\\ L((\alpha {)}^{\ast })& =L(\alpha {)}^{\ast }.\end{array}$$

Beispiele für reguläre Ausdrücke

1. $(a|b{)}^{\ast }aa(a|b{)}^{\ast }$ erzeugt alle Wörter über $\{a,b\}$, die zwei aufeinanderfolgende ‘a’s enthalten.
2. $(ϵ|((a|b|c{)}^{\ast }a(a|b|c)(a|b|c)(a|b|c)))$ erzeugt alle Wörter über $\{a,b,c\}$, die an viertletzter Stelle ein ‘a’ haben, einschließlich des leeren Worts.
3. $((0|1|2|3|4|5|6|7|8|9)|1(0|1|2|3|4|5|6|7|8|9)|(2(0|1|2|3))):((0|1|2|3|4|5)(0|1|2|3|4|5|6|7|8|9))$ erzeugt alle Wörter über $\{:,0,1,\dots ,9\}$, die Uhrzeiten im 24-Stunden-Format darstellen.

Anwendungen

Reguläre Ausdrücke werden verwendet für:

• Lexikalische Analyse in Programmiersprachen.
• Textsuche und -ersetzung in Texteditoren und Befehlszeilenprogrammen wie sed und AWK.
• Tools wie lex für C/C++, ANTLR für Java und PLY für Python generieren lexikalische Analysatoren aus regulären Ausdrücken.
• Unterstützung in modernen Programmiersprachen, entweder nativ oder durch Bibliotheken.

Theorem von Kleene

Das Theorem von Kleene besagt, dass reguläre Ausdrücke genau die regulären Sprachen erzeugen. Dies wird durch die Konstruktion spezifischer endlicher Automaten (NFA) für jeden regulären Ausdruck bewiesen, wobei gezeigt wird, dass die Sprache des Automaten der durch den regulären Ausdruck erzeugten Sprache entspricht.

Konstruktion von NFAs

• Basisautomaten: Für die Grundbausteine der regulären Ausdrücke ($\varnothing$, $ϵ$, und jedes $a\in \Sigma$) werden einfache Automaten mit einer begrenzten Anzahl von Zuständen und Übergängen erstellt.
• Operationen: Für die Operationen der Konkatenation, Auswahl und Kleene-Stern werden Kombinationen und Modifikationen der Basisautomaten beschrieben, um die entsprechenden NFAs zu bilden.

Äquivalenz und Vereinfachung

• Kommutativität: $(\alpha |\beta )=(\beta |\alpha )$
• Neutrale Elemente: $(\varnothing |\alpha )=\alpha$
• Absorption und Distributivität: Verschiedene Regeln, die die Struktur von regulären Ausdrücken vereinfachen und optimieren.

Beispiel für NFA-Konstruktionen

Konkrete Beispiele für die Konstruktion von NFAs zu gegebenen regulären Ausdrücken illustrieren die theoretischen Konzepte und demonstrieren, wie die Automaten in der Praxis gebildet werden.

Beweisstrategien für reguläre Sprachen

Diese Abschnitte behandeln die formale Beweisführung, die zeigt, dass die Sprachen, die durch reguläre Ausdrücke erzeugt werden, tatsächlich regulär sind. Dies schließt die Konstruktion spezifischer nicht-deterministischer endlicher Automaten (NFAs) ein, um zu demonstrieren, dass jede Sprache, die durch einen regulären Ausdruck definiert werden kann, auch von einem NFA akzeptiert wird.

Fortgeschrittene NFA-Beispiele

Es gibt konkrete Beispiele für NFAs, die zu komplexeren regulären Ausdrücken gehören. Diese Beispiele zeigen, wie NFAs verwendet werden, um die Operationen der Konkatenation, Auswahl und Kleene-Stern praktisch umzusetzen.

Methoden zur Vereinfachung von regulären Ausdrücken

Dieser Abschnitt behandelt verschiedene Methoden zur Vereinfachung von regulären Ausdrücken, um sie effizienter und lesbarer zu machen. Hierzu gehören die Anwendung von Gesetzen wie Kommutativität, Neutralität und Absorption.

Erweiterte Anwendungsbeispiele

Die erweiterten Anwendungsbeispiele illustrieren die vielfältigen Einsatzmöglichkeiten von regulären Ausdrücken in verschiedenen Bereichen der Computerwissenschaft und Softwareentwicklung, darunter Textverarbeitung, Datenvalidierung und die Entwicklung von Programmiersprachen.

Theoretische Untermauerung

Tiefergehende Diskussionen über die theoretische Fundierung von regulären Ausdrücken, einschließlich Beweisen zu deren Eigenschaften und Beschränkungen. Dies schließt den Satz von Kleene und dessen Implikationen für die Theorie der formalen Sprachen ein.

Theorem von Kleene

> ⊆ Wir zeigen, dass die erzeugte Sprache eines regulären Ausdrucks regulär ist. Wir konstruieren für einen regulären Ausdruck α einen NFA Mα mit ε-Übergängen und eindeutigen Start- und Endzuständen, sodass L(Mα) = L(α)

---