NF 1, SS 1997: Lösungsblatt 7: Endliche Automaten mit Ausgabe

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.

Lösung hierzu

Parität	Automat	Regulärer Ausdruck
Gerade Parität		0*(10*1)*0*
Ungerade Parität		0*10*(10*10*)*

Einige Wörter mit gerader Parität:

nats13:4727% reggen '0*10*(10*10*)*' | head -20
1
01
10
010
001
100
111
0100
0010
0001
1000
0111
1011
1101
1110
01000
00100
00010
00001
10000

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

Lösung hierzu

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

Lösung hierzu