Prof. Dr. R. Laue
WS0001
Informatik I
Übungsblatt 2
Abgabe: 2.11.00 vor der Vorlesung
URL: /axel/informatik1_ws0001_blatt2.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 4 - Schubfachprinzip - (4 Punkte)
Zeigen Sie, daß es keinen endlichen Automaten mit
dem Eingabealphabet 
= {( ,) ,x} gibt, der die Sprache
L = { (n x )n | n>0 }
akzeptiert. Hinweis: Wenden Sie das Schubfachprinzip auf
die Menge der Zustände an.
Schubfachprinzip: Hat man m>n Dinge in n Schubfächern,
so gibt es ein Schubfach mit mindestens 2 Dingen.
Aufgabe 5 - Jahreszahlenerkenner - (4+3 Punkte)
Geben Sie den Übergangsgraphen zu einem endlichen Automaten,
der gültige Jahreszahlen erkennen soll an. D.h. das Eingabealphabet
besteht aus den Ziffern 0,1,2,..,9 und dem Sonderzeichen #, welches ein
beliebiges anderes Zeichen kodiert. Die Ziffernfolge zwischen dem
Sonderzeichen # wird als Jahreszahl interpretiert. Liegt diese Zahl zwischen
1 und 2000 soll der Automat in einem Zustand aus der
Endzustandsmenge wechseln und im weiteren in diesem verbleiben. Beispiel: #345#
ist o.k. 123 ist ok 123454# ist nicht
o.k. ###11# ist ok #001# ist ok #0000#2222# ist nicht o.k.
Schreiben Sie das zugehörige 5 Tupel auf.
Aufgabe 6 - Komposition von Maschinen - (2+2+2+2 Punkte)
In der Vorlesung wurde skizziert, wie man eine endliche Maschine zur
parallelen Addition von mehreren k-stelligen Zahlen entwirft.
a) Zeichnen Sie das Blockschaltbild der endlichen Maschine
zur parallelen Addition von 16 Zahlen
b) Wieviel Takte benötigt man zur parallelen Addition
von 1048576 k-stelligen Zahlen? Ein Takt ist dabei ein Übergang (d.h.
Einlesen, Zustandwechsel) in der zugrunde liegenden Gesamtmaschine.
c) Wieviele Addierer sind in dem Schaltnetz aus b)
?
d) Wieviele verschiedene Zustände hat die Maschine aus
b) ?