Informatik zum Jahresanfang – Auflösung für 4

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Die Aufgabe ist, eine endlichen Automaten zu bauen, der sich nur dann in einem Endzustand befindet, wenn die eingegebene Zahl durch 4 teilbar ist.

Während man sich bei der Teilbarkeit durch 2 nur die letzte Stelle ansehen muss, sind es bei der Teilbarkeit durch 4 die letzten beiden. Ist die vorletzte gerade (oder nicht vorhanden), dann muss die letzte 0, 4 oder 8 sein, damit die Zahl durch 4 teilbar ist. Ist die vorletzte Stelle ungerade, dann muss dafür die letzte 2 oder 6 sein.

Ein regulärer Ausdruck, der eine durch 4 teilbare Zahl angibt, sieht also so aus: [048]|[0-9]*([02468][048]|[13579][26])^[1]

1. Reguläre Ausdrücke^[2] und endliche Automaten sind äquivalent; sie erkennen beide dieselbe Klasse von Sprachen: die regulären Sprachen (Typ 3 in der Chomsky-Hierarchie).

Der endliche Automat muss 3 Zustände haben

• letzte gelesene Ziffer ungerade;
• letzte gelesene Ziffer gerade, Zahl nicht durch 4 teilbar
• letzte gelesene Ziffer gerade, Zahl durch 4 teilbar (Endzustand)

und sieht so aus:

Diagramm von @Rolf B. Meins sah genauso aus, außer dass ich faul war und „ung.“ statt „1, 3, 5, 7, 9“ geschrieben hatte. Da kann ich mir sparen, das nochmal aufzuzeichnen und wieder Gefahr zu laufen, den Startpfeil zu vergessen.

Den Gipfel der Faulheit erreichte @Matthias Apsel, der auch die geraden Zahlen in zwei benannte Klassen {0, 4, 8} und {2, 6} einteilte und dann jeden Pfeil mit nur jeweils einem Buchstaben beschriftete.

Aber Leute: Wenn es drei Zustände gibt, wobei jeder mit jedem anderen und mit sich selbst verbunden ist, dann sollten die in der Darstellung ein gleichseitiges Dreieck bilden. Wie sieht denn das sonst aus?

Es sei denn, man macht’s wie @dedlfix und sagt: „Das Ergebnis ist ein Gesicht.“

LLAP 🖖

---

1. Die Klammern dienen hier nur zur Klammerung, nicht zum Merken von Matches. In Implementationen in Programmiersprachen wäre (?: zu schreiben. ↩︎

2. „Regulär“ wie in regulär. ↩︎