Prof. Dr. R. Laue                                                                                                                                  WS0203
                                Informatik III
                                Übungsblatt 2
                                Abgabe: 31.10. nach der Vorlesung

URL:         /axel/informatik3_ws0203_blatt2.html
Dieses  Übungsblatt ist in Zweiergruppen 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 (7 Punkte)
Beweisen Sie mittels Pumping Lemma, daß folgende Sprachen nicht regulär sind:

  • a) Zeichenketten über {a,b} mit mehr b's als a's. (3 Punkte)
  • b) Zeichenketten über {a} deren Länge eine Primzahl ist.  (4 Punkte)

    • Aufgabe 6 (2+4 Punkte)
    Geben Sie je einen nicht deterministischen endlichen Automaten (Definition und Zustandsgraph) zur Erkennung folgender Sprachen an 

  • a) binäre Zahlen, die ein Vielfaches von 4 sind. (2 Punkte)
  • b) c ((b|a*c) x)*| x*b (4 Punkte)

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