Prof. Dr. R. Laue                                                                            WS0001
                                Informatik I
                                Übungsblatt 1
                                Abgabe: 26.10. vor der Vorlesung

URL:         /axel/informatik1_ws0001_blatt1.html
Dieses  Übungsblatt ist in Zweiergruppen zu bearbeiten. Auf dem Blatt  bitte Übungsgruppentag angeben. Um den Übungsschein zu erhalten muß man 50% der Punkte erreichen und zweimal erfolgreich eine Aufgabe vorrechnen.

Aufgabe 1 - Kassenautomat - (4 Punkte)
Man definiere eine endliche Maschine (d.h. Angabe des 6 Tupels), die bei Einwurf von Münzen (0.5 Euro, 1 Euro, 2 Euro, 5 Euro) in beliebiger Reihenfolge anzeigt, welcher Betrag noch eingeworfen werden muß um 7 Euro zu erreichen, bzw bei Erreichen von 7 Euro Einlaß gewährt. Es soll keine Rückgabe von Geld erfolgen. Man berücksichtige auch das Problem, wie die Maschine merkt, daß ein neuer Mensch Einlaß begehrt.

Aufgabe 2 - Addierer - (2+4 Punkte)

  • Zeichnen Sie die Folge der Zustände und die Ausgabe bei der binären Addition von 11100110 = 0*20 + 1*21 + 1+22 + 0*2^3 ... und 10101001 mit Hilfe des in der Vorlesung definierten binären Addierwerks. Geben Sie diese Definition mit an.  Was ist der erreichte Zustand?  Wieviel Zustandswechsel finden statt?
  • Analog zum binären Addierwerk kann man ein  Addierwerk zur Addition von zwei Zahlen im Ternärsystem definieren. Geben Sie eine Definition an und führen Sie eine Beispieladdition mit Ihren beiden Matrikelnummern modulo 1000  im Ternärsystem durch.

    •  

     

    Aufgabe 3 - Übergangsgraph, Erkennen von Sprachen- (3+3 Punkte)
     

  • Geben Sie einen endlichen Automaten an , der die Sprache L = { a3b3bmcna2 | n>=0 , m>=0 } hat. D.h. nach Eingabe eines Wortes der Sprache soll der Automat in einem Zustand aus der Menge der Endzustände sein. Zeichnen Sie den Übergangsgraph.
  • Gegeben sei der folgende Übergangsgraph
    • S sei der Startzustand, C der einzige akzeptierende Zustand. Definieren Sie den zugehörigen endlichen Automaten (1 Punkt), was ist die akzeptierte Sprache? (2 Punkte)