Prof. Dr. R. Laue                                                                                                                                  WS9900                                 Informatik I
                                Übungsblatt 1
                                Abgabe: 16.11.99 vor der Vorlesung

URL: /axel/informatik1_ws9900_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 (1 Euro, 2 Euro, 5 Euro) in beliebiger Reihenfolge anzeigt, welcher Betrag noch eingeworfen werden muß um 8 Euro zu erreichen, bzw bei Erreichen von 8 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 10100110 = 0*2⁰ + 1*2¹ + 1+2² + 0*2^3 ... und 10001001 mit Hilfe des in der Vorlesung definierten binären Addierwerks. Geben Sie diese Definition mit an.

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 durch.

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

Geben Sie einen endlichen Automaten an , der die Sprache L = { a²b^mcⁿa² | n>=0 , m>=0 } akzeptiert. 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)