Wie man eine Aufgabe löst.
Aufgabe: Geben Sie einen regulären Ausdruck an, der alle binären Zahlen akzeptiert, die durch 4 teilbar sind.
Vorgehen: Schreibe zunächst die ersten 10 Zahlen in Binärdarstellung auf, die durch 4 teilbar sind um ein Muster zu erkennen, dass sich als regulärer Ausdruck darstellen lässt:
– 100
– 1000
– 1100
– 10000
– 10100
– 11100
– 100000
– 100100
– 101100
– 110000
Lösung: Das Muster lässt sich in mehreren Phasen erkennen. Die letzten beiden Stellen bilden immer zwei Nullen. Dann folgen immer die selben Muster aus zwei Stellen. Entweder eine 10, eine 11, eine 00 oder eine 01. Wenn man nun also die beiden Erkenntnisse zusammenführt, hat man folgenden regulären Ausdruck:
–> (00+01+10+11)*00
Tagebuch 