NF 1, SS 1997: Übungsblatt 7: Endliche Automaten mit Ausgabe

Ausgegeben am:27. Mai 1997
Abzugeben bis:3. Juni 1997
Lösungen dazu

Aufgabe 1: Paritätsprüfung

Die Einführung einer Parität erlaubt die Erkennung von Ein-Bit-Fehlern in Speicherwörtern. Dazu wird ein zusätzliches Bit für jedes Speicherwort (z.B. für jedes Byte) angelegt, so daß die Anzahl der gesetzten Bits immer gerade (oder ungerade) ist. Dadurch kann in begrenztem Umfang die Konsistenz des Speichers gewährleistet werden.

Außerdem kann bei Übertragung über unsichere Kanäle ein gewisses Maß an Sicherheit erreicht werden.

Entwerfen Sie einen endlichen Automaten, der eine beliebig lange Bitfolge einliest und das Wort akzeptiert, wenn es gerade (ungerade) Parität hat.

Wandeln Sie den endlichen Automaten in einen regulären Ausdruck um und generieren Sie einige Wörter.

Aufgabe 2: Addition mit endlichen Automaten

In der Vorlesung war die Multiplikation von Binärzahlen besprochen worden. Entwerfen Sie einen endlichen Automaten, der die Addition von Binärziffern leistet. Der Zahlenbereich für die Resultate soll sich dabei von 0 bis 4 erstrecken.

Beispiel: 0 + 1 + 0 + 1 + 1 = 3

Aufgabe 3: Addition und Multiplikation mit endlichen Automaten

Kombinieren Sie den in Aufgabe zwei entworfenen Additionsautomaten mit dem Multiplikationsautomaten aus der Vorlesung, so daß gemischte Aufgaben vorkommen können, z.B.

0 + 1 * 1 + 1 * 1 + 1 + 0 = 3