SLP Notizen

Teil I
Kapitel 2: Reguläre Ausdrücke und Automaten

Inhalt

1. Reguläre Ausdrücke
• suchen und ersetzen in Perl
• Nutzung zum Beispiel in ELIZA mittels Kaskaden von RegExps
• simpel und für simple Aufgaben benutzbar (pattern-matching)
• äquivalent zu endlichen Automaten, regulären Sprachen
• Speicher (\1) ist formal nicht Teil von endlichen Automaten
2. endliche Automaten (finite-state automata)
• jeder endliche Automat besteht aus:
• endlicher Zustandsmenge Q
• endliches Alphabet Σ
• Startzustand q₀
• Menge der Endzustände F ⊆ Q
• Übergangsfunktion δ: Q × Σ → Q für deterministische Automaten bzw.
• Übergangsrelation δ: Q × Σ → 2^Q für nichtdeterministische Automaten
• Automaten "akzeptieren" Wörter über dem Alphabet, ihre Sprache
• Akzeptierung lässt sich über Suche im Zustandsraum des Automaten prüfen
• Tiefensuche -> terminiert nicht bei rekursiven Regeln
• Breitensuche -> braucht zu viel Speicher, terminiert auch nicht immer
• dynamische Programmierung
• A^*-Suche
• nichtdeterministische Automaten sind äquivalent zu deterministischen Automaten, d.h. zu jedem NFSA lässt sich ein DFSA konstruieren
3. reguläre Sprachen und endliche Automaten
• äquivalent
• auch endliche Automaten lassen sich vereinigen, schneiden voneinander abziehen, komplementieren
• übliches Vorgehen: reguläre Ausdrücke werden in einen DFSA kompiliert, der effizient und schnell die Zugehörigkeit eines Worts zur Sprache prüfen kann

letzte Änderung: 19. Juli 2006.