Übung Reguläre Ausdrücke
einfach
Aufgabe 1
Beschreiben Sie die Menge L* aus dem zweiten Beispiel von Kapitel 1 durch einen regulären Ausdruck. (Geben Sie das Syntaxdiagramm an.)
Aufgabe 2
Begründen Sie die folgenden Eigenschaften von regulären Ausdrücken. Hierbei heißen zwei reguläre Ausdrücke r und s gleichwertig, geschrieben r = s, wenn sie dieselben Mengen bezeichnen, wenn also L(r) = L(s) gilt.
- r|(s|t) = (r|s)|t
- r|s = s|r
- r(s|t) = rs|rt
Begründen Sie, dass rs = sr im Allgemeinen falsch ist.
nicht ganz so einfach
Aufgabe 3
Beschreiben Sie folgende Wortmengen über dem Alphabet X={a,b} durch je einen regulären Ausdruck. (Geben Sie jeweils das Syntaxdiagramm an.)
- Die Menge aller Worte, die mit a beginnen und mit b enden.
- Die Menge aller Worte, die mit a beginnen oder mit b enden, einschließlich a und b.
- Die Menge aller Worte, die wenigstens drei aufeinander folgende a enthalten.
- Die Menge aller Worte, bei denen jedem b ein a folgt.
Aufgabe 4
Beschreiben Sie umgangssprachlich die durch folgende reguläre Ausdrücke bezeichneten Wortmengen über {a,b}. Entwerfen Sie jeweils ein Syntaxdiagramm und einen endlichen Akzeptor für diese Sprachen.
- (aba)*
- (aa|b)*(a|bb)*
- [ab]*aa[ab]*
- [ab]+bba
Aufgabe 5
Gegeben sei der reguläre Ausdruck über X= {a,b,u,v,w} mit [ab](uv)*ww*[ab].
- Vereinfachen Sie.
- Beschreiben Sie diesen regulären Ausdruck mit Hilfe eines Syntaxdiagramms.
- Konstruieren Sie einen Automaten, der die zugehörige Sprache akzeptiert. Geben Sie ihn im mathematischen Sinne und in Form eines Graphen an.
- Beschreiben Sie die Worte, die zur beschriebenen Sprache gehören.
Aufgabe 6
Entwerfen Sie einen endlichen Akzeptor, der die durch a[ab]*aa(ca)* bezeichnete Sprache erkennt.
Aufgabe 7
Geben Sie zu dem vorliegenden Akzeptor ein geeignetes Syntaxdiagramm und einen regulären Ausdruck an.
