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.