Informatik zum Jahresanfang – noch mehr Teiler - Spoiler

[Gunnar Bittersmann]

@@dedlfix

Vermutlich lassen sich alle diese Automaten nach demselben sehr einfachen Prinzip erstellen.

Ich bin vielleicht der letzte, der’s verstanden hat; aber ich glaube, jetzt hab auch ich es. Um nicht ganz so dumm dazustehen, konter ich mit der nächsten (letzten?) Aufgabe:

Baue einen endlichen Automaten, der eine durch n teilbare Zahl erkennt. Für den allgemeinen Fall soll die Einschränkung fallengelassen werden, dass es der Minimalautomat sein muss.

Mit einem Diagramm wird das bei beliebigem n wohl nichts, gesucht ist die formale Darstellung als Quintupel (S, s₁, Σ, δ, F) (siehe Ursprungsposting). Das Alphabet Σ ist klar, wie gehabt Ziffern 0 bis 9. Wie sieht die Zustandsmenge S aus? (Größe – Namen sind Schall und Rauch.) Und wie die Übergangsfunktion δ?

LLAP 🖖

PS: Abgesehen davon stehen immer noch die Minimalautomaten für 3, 6 und 15 im Raum. Auf die kommt man vermutlich einfacher durch Überlegungen auf direktem Weg als vom allgemeinen Fall auszugehen und dann die Zustandsmenge zu reduzieren.