FGI-1 – Formale Grundlagen der Informatik I

FGI-1 – Formale Grundlagen der Informatik I
Logik, Automaten und Formale Sprachen
Aufgabenblatt 1 : Formale Sprachen und Automaten
Präsenzteil am 5.-8. April – Abgabe am 12.-15. April 2016
Präsenzaufgabe 1.1:
1. Wir betrachten das Alphabet Σ = {a, b, c} und die Teilmengen X, Y, Z ⊆ Σ∗ mit X =
{a, ab, λ}, Y = {c, bc, ac} und Z = {c, cc}.
(a) Bestimmen Sie X × Y und |X × Y |.
(b) Bestimmen Sie X · Y und |X · Y |.
(c) Bestimmen Sie Z 0 ∪ Z 1 ∪ Z 2 .
2. Sei Σ ein Alphabet und A, B, C ⊆ Σ∗ beliebige Sprachen. Beweisen oder widerlegen Sie
folgende Gleichungen, indem Sie zwei (!) Inklusionsbeziehungen beweisen oder ein Gegenbeispiel angeben.
(a) (A ∪ B)∗ = A∗ ∪ B ∗
(b) (A ∪ B) · C = (A · C) ∪ (B · C)
Präsenzaufgabe 1.2:
Gegeben sei der folgende deterministische, endliche Automat A:
0,1
2 zOe l
0
0
1
/ zs
1
/ z1 j
0
)z
2
1
1. Geben Sie die formale Notation des DFA A an.
2. Geben Sie die Rechnung auf dem Wort 10101 und die Rechnung auf dem Wort 10110 an.
Welche dieser Rechnungen ist eine Erfolgsrechnung?
3. Emil Eilig behauptet, dass die vom Automaten akzeptierte Sprache M = {1}·({0}·{1})∗ ist.
Beweisen Sie, dass tatsächlich L(A) = M gilt, indem sie zwei Mengeninklusionen beweisen.
Übungsaufgabe 1.3: Gegeben die formalen Sprachen L1 = {0i | i ∈ N} = {0}∗ , L2 = {1i | i ∈
N} = {1}∗ und L3 = {(01)i | i ∈ N} = {01}∗ über dem Alphabet Σ = {0, 1}. Berechnen Sie die
nachfolgenden Mengen. Geben Sie Ihr Ergebnis dabei möglichst kurz an. So ist z.B. {0} besser
als {0, 1} \ {1}. (Geben Sie hier lediglich das Ergebnis an, ein strenger Gleichheitsbeweis ist nicht
nötig. Sie können Ihr Ergebnis aber begründen, wenn es Ihnen nötig erscheint.)
von
4
1. L3 ∩ Σ∗
2. L3 ∪ Σ∗
3. L1 ∩ L2
4. L3 \ L1
5. Σ∗ \ L1
6. (L3 ∪ L1 ) ∩ Σ4
7. {0} · Σ∗ · {1}
8. L1 · Σ∗ · L2
Übungsaufgabe 1.4: Gegeben sei der folgende deterministische, endliche Automat A, für den
wir die akzeptierte Sprache bestimmen wollen.
0,1
0
/ z0
von
4
1
c
#
1
z1
&
z2
0
Emil Eilig meint wieder, die Lösung zu kennen. Er behauptet L(A) = {0, 1}∗ · {11} · {0, 1}∗ =: M .
Zeigen Sie, dass dies tatsächlich stimmt.
Hinweis: Achten Sie besonders darauf, die zwei Richtungen beim Beweis der Mengengleichheit
sauber zu trennen. Werfen Sie ggf. noch einmal einen Blick in die Lösung der Präsenzaufgaben.
Übungsaufgabe 1.5: Sei M = (({0} · {1}) ∪ {1})∗ . Konstruieren Sie einen deterministischen,
endlichen Automaten A mit L(A) = M und beweisen Sie, dass dies tatsächlich gilt.
Informationen und Unterlagen zur Veranstaltung unter:
http://www.informatik.uni-hamburg.de/TGI/lehre/vl/SS16/FGI1
Version vom 1. April 2016
Bisher erreichbare Punktzahl :
12
von
4

Download Report