Hallo Gunnar Bittersmann,

Falls es auch eine Dezimalzahl sein soll, bin ich auf die Lösung gespannt.

Gemeint ist Zahl im Dezimalsystem.

Ich bin eher gespannt, wie’s dann mit 16, 32, … weitergeht. Aber schön der Reihe nach …

Ich betrachte mich als an 8 gescheitert.

Bis demnächst
Matthias

@@dedlfix

Darstellung analog zur dedlfixschen Gesichtsform beim 4er: ein keltisches Ornament?

(Fehlende Beschriftung gewollt, aber ich hab mal wieder keinen Startpfeil gemalt und der Übergang vom Endzustand zu sich selbst fehlt. Aber das würde nur die Symmetrie stören. 😉)

Denk mal dreidimensional. Der Bogen zeigt in Richtung Z-Achse, dann kannst du das Ding drehen, daran aufhängen, und 4 Kerzen in die Zustände stecken. So erhält man einen schönen Adventskranz für informatisch Interessierte.

(3D-Modell)

Soll in die Mitte auch eine Kerze?

Und wenn das 5. Lichtlein brennt, haste Weihnachten verpennt?

LLAP 🖖

Hallo Gunnar Bittersmann,

?? Nee, [048] da vornedran ist für die einstelligen 0, 4 und 8.

Schon klar.

… und den Automaten damit auf drei Zustände reduziert.

?? Der reguläre Ausdruck hat mit den Zuständen eines entsprechenden endlichen Automaten zunächst einmal wenig zu tun.

Meine erster Automat hatte noch 5 Zustände.

Bis demnächst
Matthias

@@Matthias Apsel

der für 7 ist auch immer noch offen

Die wollte ich mir für zum Schluss aufheben.

Wenn man vergisst, dass es Teilbarkeitsregeln gibt, kann man alle diese Automaten nach demselben Muster bauen.

Kann man? Ich würde sagen: nein.

Also gut, dann eröffnen wir auch diese Runde: … Automat, der durch 7 teilbare Zahlen erkennt. Oder beweise, dass es keinen solchen gibt. In anderen Worten: zeige, dass die Sprache der durch 7 teilbaren Zahlen regulär ist bzw. dass sie das nicht ist.

LLAP 🖖

Hallo Gunnar Bittersmann,

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.

Diese Aufgabe ist nicht lösbar.

Du kannst höchstens für ein konkretes n einen Automaten bauen, nicht aber einen Automaten, der Teilbarkeit durch beliebige n erkennt.

Bis demnächst
Matthias

Tach!

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.

Meinst du, die lassen sich mit weniger als 4 Zuständen realisieren?

dedlfix.

Hallo Gunnar,

Ich bin vielleicht der letzte, der’s verstanden hat; aber ich glaube, jetzt hab auch ich es.

Nein, bist Du nicht, ich glaube, ich war's. Aber dafür versuche ich jetzt mal, es aufzuschreiben, am Beispiel der 7.

Man braucht für einen solchen Automaten einen Startzustand sowie einen Zustand R0 bis Rn für jeden möglichen Divisionsrest. Die Werte der Übergangsfunktion des Startzustandes sind identisch mit denen des Endzustandes. Er existiert nur, damit das leere Wort nicht als "teilbar durch N" akzeptiert wird. Endzustand ist logischerweise R0.

Man muss nun herausfinden, wie sich k und 10k mod 7 verhalten:

Wenn $k \equiv n \pmod 7$, dann ist $10k = 7k+3k \equiv 0 + 3n \pmod 7$. Mit $p = (3n \bmod 7)$ erhält man also den Status Rp, der bei Antreffen der Ziffer 0 auf den Rn folgen muss. Die übrigen ergeben sich fortlaufend automatisch: Zum Beispiel ist p=5 für n=4, damit hat der Zustand R4 die Übergänge

Oder - aus FLACI kopiert, diese Deltafunktion:

Ob das bei zweistelligen Teilern genauso funktioniert? Wenn $k \equiv n \pmod{37}$, was ist dann mit 10k?

$10k = 37k - 27k \equiv 0 - 27n \pmod{37}$, d.h. für $p=(-27n) \bmod 37$ erhält man zum Status n den Folgestatus p bei Antreffen der Ziffer 0. Dabei ist der Rest so zu bestimmen, dass er nicht negativ ist, d.h. es muss beispielsweise $-27 : 37 = -1$ mit Rest 10 gelten.

Auf den Zustand R1 müsste bei Antreffen der Ziffer 0 also der Zustand $-27\cdot 1 \bmod{37}= 10$ folgen, demzufolge bei Antreffen der 4 der Zustand R14. Und auf R14 der Zustand $-27\cdot 14 \bmod{37}=29$ für Ziffer 0, demzufolge R0 für Ziffer 8. Kurzer Blick auf den Taschenrechner: $148=4\cdot 37$ - scheint zu passen.

Ich bin total perplex, das hatte ich für unmöglich gehalten.

Rolf

@@Gunnar Bittersmann

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 δ?

Ich glaube, alle Zutaten wurden bereits im Thread zusammengetragen. Ab in den Topf damit, umgerührt – fertig ist die Suppe – äh der Automat.

Eine Zahl lässt bei der Division durch n den Rest r, wobei 0 ≤ r < n. Es gibt also n Restklassen 0, 1, …, n − 1. Diese bilden wir beim Automaten durch n Zustände $s_0, s_1, \ldots, s_{n-1}$ ab. Der Automat soll sich im Zustand sᵤ befinden, wenn die bis dahin gelesene Zahl bei der Division durch n den Rest u lässt. Der Zustand s₀ steht für die Restklasse 0, d.h. wenn der Automat im Zustand s₀ ist, dann ist die eingelesene Zahl durch n teilbar. s₀ ist also der einzige Endzustand.

Außerdem brauchen wir – wie wir am Beispiel mit der 3 gesehen haben (und am Beispiel mit der 9 nicht gesehen haben 😆) – einen zusätzlichen Startzustand. Diesen bezeichne ich hinterlistigerweise mit s₋₀. Der ist genauso „verdrahtet“ wie s₀, d.h. für alle Eingaben d sind die Folgezustände für s₀ und s₋₀ jeweils gleich: δ(s₀, d) = δ(s₋₀, d).

Wie sieht nun die Übergangsfunktion δ aus? Der Automat sei nach Einlesen der Eingabefolge $d_{-k}, d_{-k+1}, \ldots, d_{-1}, d_0$ (mit dᵢ ∈ Σ = {0, 1, …, 9}) – also der Zahl $z_0 = d_{-k}d_{-k+1}…d_{-1}d_0$ – im Zustand sᵤ. Das heißt z₀ ≡ u mod n oder, um noch eine weitere Schreibweise zu bemühen: z₀ mod n = u. (mod ist hier ein Operator; entspricht genau dem %-Operator in JavaScript.)

Durch Einlesen der nächsten Ziffer d₁ entsteht die neue Zahl $z_1 = d_{-k}d_{-k+1}…d_{-1}d_0d_1 = 10 z_0 + d_1$. Für diese gilt:

z₁ = 10z₀ + d₁ ≡ 10u + d₁ ≡ v mod n (mit 0 ≤ v < n)

Das ist das ganze Geheimnis, deshalb spendiere ich hierfür Fettschrift und eine eigene Zeile. Anders gesagt: v = (10u + d₁) mod n ist die Restklasse der neuen Zahl z₁; sᵥ ist der Folgezustand.

Und weil die Rechnung für 0 und −0 dieselbe ist, hatte ich den Startzustand so benannt.

Der Folgezustand sᵥ hängt also nur vom vorigen Zustand sᵤ und der Eingabe d₁ ab; die vorherigen Eingaben $d_{-k}, d_{-k+1}, \ldots, d_{-1}, d_0$ muss man dazu nicht kennen. Das ist genau der Grund, warum die Erkennung der Teilbarkeit durch n mit einem endlichen Automaten möglich ist; ein endlicher Automat hat ja kein „Gedächtnis“ für die Vergangenheit.

Damit haben wir unsere Übergangsfunktion δ(sᵤ, d) = sᵥ mit v = (10u + d) mod n; und damit haben wir unseren Automaten:

LLAP 🖖

Nachtrag: Der Automat ist nicht notwendigerweise minimal, d.h. es können evtl. Zustände zusammengefasst werden. Es steht die Vermutung im Raum, dass der Automat für n prim minimal ist und für n zusammengesetzt nicht.

Nachtrag 2: dedlfix hatte schon einen Automaten vorgestellt, der für einige n mit weniger als n + 1 Zuständen auskommt, aber auch nicht notwendigerweise minimal ist. Lässt sich jener auch so einfach formal beschreiben?

@@dedlfix

Und wenn man zwei 10er hinternander setzt, erhält man einen Automaten, der durch 100 teilbare Zahlen erkennt.

Auch der ensteht, wenn ich nach "meinem" Prinzip vorgehe, mit 9 plus 2 Zuständen. Allerdings konnte der Flaci den auf drei Zustände minimieren.

Bei der Million sind’s sieben Zustände. Allgemein: bei 10ⁿ sind’s n + 1. Bei 100 also 3.

LLAP 🖖

Hallo dedlfix,

uff, das habe ich jetzt auf Anhieb nicht verstanden. Meine Herleitung mit Modulo-Rechnung gefällt mir spontan besser :)

Und der Argumentation hier:

Man braucht für Primzahlen n Zustände plus den E, bei Nicht-Primzahlen sind es weniger, weil Vielfache von ihnen durch 10 teilbar sind.

vertraue ich erstmal nicht. Es scheint mir eher so, dass bei Nichtprimzahlen sich die Werte der Übergangsfunktion bei unterschiedlichen Resten wiederholen (gerade mal mit der 6 durchgezogen, nach "meinem" Prinzip waren es Knoten R0 bis R5 (auf den separaten Startknoten hatte ich verzichtet), nach Optimierung hatte er die Knoten R1+R4 und R2+R5 zusammengefasst. R0 und R3 blieben separat, das hat er ordentlich herausbekommen.

Rolf

Tach!

‚Aber Gunnar‘, werdet ihr sagen, ‚Anfangs- und Endzustand müssen doch aufgedröselt sein!‘

„Marty, du musst vierdimensional denken!“ Hier reicht eine weniger, wie dedlfix sagte: „Denk mal dreidimensional.“

Hab ich gemacht und in 3D gezeichnet: Anfangs- und Endzustand befinden sich in der Projektion genau hintereinander und damit überlappen sich auch ihre Verbindungen zu den anderen Zuständen und deren identischen Beschriftungen! 😜 (Die Ausrede konnte ich nicht an andere verschenken, die brauchte ich für mich selber.)

Geht nicht. Wenn es mehrere Ebenen gibt, kann man die nicht durch zeichnerische Projektion eliminieren. An dieser Stelle gibt es keine künstlerische Freiheit. Oder kannst du diesen Automaten bauen, ohne Speicher für einen weiteren Zustand zu verwenden?

dedlfix.

@@Gunnar Bittersmann

Das Neuneck mit Diagonalen hatte ich eigentlich für die Teilbarkeit durch 16 angedacht.

Was auch ’ne faule Ausrede ist.

Da ich faul bin: machen lassen – von einem Script.

Eben. Einfach in selbigem bei const n = 9; (ich bin ja nicht ganz doof 😜) die 9 durch 10 ersetzt und schon generiert es ein Dekagon mit all seinen Diagonalen.

LLAP 🖖

Tach!

Wie müsste man den Automaten verändern, wenn führende Nullen nicht erlaubt sind?

Erstellst du S0 als Start und leitest alle 0-Eingaben auf einen Fehler-Zustand

Alle 0-Eingaben? Nein! Eine unbeugsame hört nicht auf, dieser Regel Widerstand zu leisten.

Da S0 nur für die erste Ziffer zuständig ist, sind nicht alle 0-Eingaben betroffen, sondern nur Eingaben, die mit 0 anfangen (und beliebig weitergehen).

dedlfix.

Hallo Gunnar Bittersmann,

Örks. Wenigstens einer versteht mich. 😉

Erstelle einen Automaten über dem Alphabet {0; 1; 2; 3; 4; 5; 6; 7; 8; 9; -; ,}, der erkennt, ob die eingegebene Zahl eine gültige Zahl ist. Gültig im Sinne von: Darf so im Heft eines Schülers stehen.

Bis demnächst
Matthias