Vorlesung Informatik 3 Einführung in die Theoretische Informatik (05 – Reguläre Ausdrücke)Prof. Dr. Th. Ottmann
Vorlesung Informatik 3 Einführung in die Theoretische Informatik (05 – Reguläre Ausdrücke)
Prof. Dr. Th. Ottmann
Motivation für reguläre Ausdrücke
Ziel: Automatenfreie Charakterisierung der regulären Sprachen, also der von endlichen Automaten akzeptierbaren Mengen von Worten.
Kompakte Notation zur Bezeichnung von regulären Sprachen.
Unterschied: Regulärer Ausdruck α (Bezeichnung, syntaktisches Konzept) und die von einem regulären Ausdruck α bezeichnete Menge L(α) von Worten (semantisches Konzept).
Reguläre Sprachen besitzen Abgeschlossenheitseigenschaften gegenüber Operationen an Mengen von Worten.
Reguläre Sprachen haben viele Anwendungen, sind aber leider sehr beschränkt.
Reguläre Ausdrücke
Wir definieren simultan, was unter einem regulären Ausdruck α über dem Alphabet und der von α bezeichneten Menge L(α) * verstanden wird:
Sei ein endliches Alphabet.
ist ein regulärer Ausdruck über und L() = .
ε ist ein regulärer Ausdruck über und L(ε) = {ε}.
Für jedes a ist a ein regulärer Ausdruck über und L(a) = {a}.
Sind α und β reguläre Ausdrücke über , so auch (α β), (α β), α* und
L((α β)) = L(α) L(β)
L((α β)) = L(α) L( β)
L(α* ) = (L(α))*
Konvention: Klammern dürfen weggelassen werden, wenn keine Missverständnisse zu befürchten sind.
Bemerkungen und Beispiele
Konstruktion von DFAs zu regulären Ausdrücken
Satz 1: Zu jedem regulären Ausdruck α über dem Alphabet kann man einen DFA A = (Q, , δ, s0, F) angeben mit L(A) = L(α).
Bew.: Durch Induktion über den Aufbau von α.
(1) Sei α = . Dann ist L(α) = L(A) für den wie folgt definierten DFA A:
(2) Sei α = ε. Dann ist L(α) = L(A) für den wie folgt definierten DFA A:
(3) Sei α = a, mit a .
Dann ist L(α) = L(A) für den wie folgt definierten DFA A:
(4) Hat man bereits DFAs A und B, die die von α und β bezeichneten
Mengen L(α) und L(β) akzeptieren, also L(A) = L(α) und L(B) = L(β),
so kann man offensichtlich DFAs konstruieren, die
L((α β)) = L(α) L(β)
L((α β)) = L(α) L( β)
L(α* ) = (L(α))* akzeptieren. Denn die Klasse der regulären Sprachen ist abgeschlossen
gegenüber Vereinigung, Verkettung und Kleene Stern!
Beispiel
Gegeben sei der reguläre Ausdruck α = (ab a)* über dem Alphabet {a, b}.
Konstruktion eines regulären Ausdrucks zu DFA
Satz: Zu jedem DFA A =(S, , δ, s1, F) kann man einen regulären Ausdruck α angeben mit L(A) = L(α).
Weitere Abschlusseigenschaften
Sei für ein Wort w = a1a2 … an, n ≥ 0, w *, das Spiegelbild sp(w) definiert durch sp(w) = anan-1 … a1.
Satz: Zu jedem regulären Ausdruck α über kann man einen regulären Ausdruck αsp angeben, so dass L(αsp ) = {sp(w); w L(α)}
Comments