Prof. Dr. R. Laue                                                                                                                                  WS0203
                                Informatik III
                                Übungsblatt 1
                                Abgabe: 24.10. nach der Vorlesung

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

Aufgabe 1 (13 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 ungeraden 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. Dabei ist die Ziffer der niedrigsten 2-er Potenz rechts geschrieben. (2 Punkte)
  • e) Zeichenketten über {a,b,c}, die die Teilzeichenkette aabaabc enthalten.(2 Punkte)
  • f) nicht negative Integer Konstanten in C, die entweder in Dezimal oder Oktalschreibweise (siehe C-Manual) gegeben sind. (2 Punkte)
  • g) Nachnamen aller Bundeskanzler der Bundesrepublik Deutschland (1 Punkt)
  • h) Alle 6-stelligen Zahlen, die man aus den Ziffern ihrer 6-stelligen Matrikelnummer bilden kann. (2 Punkt)


    • 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 b's als a's. (3 Punkte)
  • b) Zeichenketten über {p,a,l}, 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 (2+2+3 Punkte)
    Geben Sie je einen endlichen Automaten (Definition und Zustandsgraph) zur Erkennung der Sprachen aus 1b,1e,1h an.