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

Aufgabe 4 (10 Punkte)
Eine Sprache heißt regulär, wenn sie durch einen regulären Ausdruck beschreiben werden kann, oder
was equivalent ist durch einen endlichen Automaten akzeptiert wird. Beweisen Sie das Pumping Lemma
für reguläre Sprachen:
Sei L eine reguläre Sprache, dann gibt es eine Konstante n, sodaß jedes Wort z aus L mit >=  n Buchstaben
geschrieben werden kann als z = uvw (Produkt = hintereinander Schreiben von Teilworten) wobei die Länge von
uv  <= n und die Länge von v >= 1 ist. Es gilt dann für alle i >= 0:
    u v^i w  liegt auch in L
Tip: n hat was mit der Anzahl der Zustände des Automaten zu tun.
 

Aufgabe 5 (6 Punkte)
Beweisen Sie:
Die Sprache L = { a^q | q ist ein Quadrat natürlicher Zahlen >= 1} ist nicht regulär.
 

Aufgabe 6 (2+4 Punkte)
Gebe zu folgenden reguläre Ausdrüken einen nichtdeterministischen endlichen Automaten (Angabe der  vollständigen Definition)  mit gleicher Sprache an:

a) (if|then|else)  (2 Punkte)
b) a ((b|a*c) x)*|x*a (4 Punkte)

Aufgabe 7 (6 Punkte)
Wandle den nichtdeterministischen endlichen Automaten aus Aufgabe 6b
in einen deterministischen endlichen Automaten um.