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 \mid (s \mid t) = (r \mid s) \mid t
- r \mid s = s \mid r
- r(s \mid t) = rs \mid rt
Begründen Sie, dass rs = sr im Allgemeinen falsch ist.
Aufgabe 3
Beschreiben Sie folgende Wortmengen über dem Alphabet X = \{a, b\} durch je einen regulären Ausdruck. (Geben Sie jeweils auch das Syntaxdiagramm und einen geeigneten Akzeptor 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 \mid b)^{*}(a \mid 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 den regulären Ausdruck.
- 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.
