Prof. Dr. R. Laue                                                                                                                                  WS9899                                 Informatik III
                                Übungsblatt 1
                                Abgabe: 9.11.98 nach der Vorlesung

URL: /axel/informatik3_ws9899_blatt1.html
Dieses Übungsblatt ist alleine zu bearbeiten.

Aufgabe 1 (10 Punkte)
Geben Sie reguläre Ausdrücke an für folgende Sprachen:

a) Zeichenketten über {a,b,c}, wo das erste a vor dem ersten b kommt.(1 Punkt)

b) Zeichenketten über {a,b,c} mit einer geraden Anzahl von a.(2 Punkte)

c) binäre Zahlen, die ein Vielfaches von 4 sind. (1 Punkt)

d) binäre Zahlen, die größer als 101001 sind.(2 Punkte)

e) Zeichenketten über {a,b,c}, die nicht die Teilzeichenkette baa enthalten.(2 Punkte)

f) nicht negative Integer Konstanten in C, die entweder in Dezimal oder Oktalschreibweise (siehe C-Manual) gegeben sind. (2 Punkte)

Aufgabe 2 (10 Punkte)
Beweisen Sie, daß folgende Dinge nicht von einem endlichen Automaten erkannt werden können:

a) Zeichenketten über {a,b} mit mehr a's als b's. (3 Punkte)

b) Zeichenketten über {a,b}, die Palindrome sind, d.h. vorwärts und rückwärts gelesen ergeben sie das gleiche Wort (3 Punkte)

c) die Menge der syntaktisch korrekten C Programme. (4 Punkte)

Aufgabe 3 (6 Punkte)
Geben Sie einen endlichen Automaten (Definition und Zustandsgraph) zur Erkennung der Sprachen aus
1b und 1e an.