Informatik zum Jahresanfang

[Gunnar Bittersmann]

Das Bild zeigt einen endlichen Automaten, der sich bei der Eingabe einer Ziffernfolge nur dann im Endzustand (dargestellt durch doppelte Linie) befindet, wenn die dadurch eingegebene Zahl durch 2 teilbar ist. (Führende Nullen sollen erlaubt sein.)

1. Formal beschrieben ist dieser durch ein Quintupel (S, s₁, Σ, δ, F) mit:
   S – Menge der Zustände, in dem Fall S = {s₁, s₂}
   s₁ ∈ S – Startzustand
   Σ – Menge der Eingabesymbole (Eingabealphabet), in dem Fall Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
   δ: S × Σ → S – Zustandsübergangsfunktion, in dem Fall $$\delta(s_i, \sigma) = \begin{cases} s_2, & \text{wenn }\sigma ∈ {0, 2, 4, 6, 8}
   s_1, & \text{wenn }\sigma ∈ {1, 3, 5, 7, 9} \end{cases}; i ∈ {1, 2}$$
   F ⊆ S – Menge der Endzustände, in dem Fall F = {s₂}

Die Aufgabe ist, einen endlichen Automaten zu bauen, der sich nur dann in einem Endzustand befindet, wenn die eingegebene Zahl durch 4 teilbar ist. Grafische Darstellung genügt. (Wie oben: führende Nullen sind erlaubt.)

LLAP 🖖

[Matthias Apsel]

Hallo Gunnar Bittersmann,

[Bild gelöscht]

Der Startzustand wird durch einen zum Zustand zeigenden Pfeil symbolisiert.

Bis demnächst
Matthias

[Gunnar Bittersmann]

@@Matthias Apsel

Der Startzustand wird durch einen zum Zustand zeigenden Pfeil symbolisiert.

Grmpf, natürlich. Den hatte ich vergessen. Jetzt ergänzt.

LLAP 🖖

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Das Bild zeigt einen endlichen Automaten, der sich bei der Eingabe einer Ziffernfolge nur dann im Endzustand (dargestellt durch doppelte Linie) befindet, wenn die dadurch eingegebene Zahl durch 2 teilbar ist. (Führende Nullen sollen erlaubt sein.)

Erklärung, wie das zu verstehen ist; am Beispiel von 9876:

Der Automat ist anfangs im Zustand s₁; das ist kein Endzustand.

Durch Eingabe einer 9 bleibt der Automat im Zustand s₁. Kein Endzustand; 9 ist nicht durch 2 teilbar.

Durch Eingabe einer 8 geht der Automat in den Zustand s₂. Das ist ein Endzustand; 98 ist durch 2 teilbar.

Durch Eingabe einer 7 geht der Automat wieder in den Zustand s₁. (Das kann er tun. Endzustand heißt, dass der Automat am Ende in dem Zustand sein kann; nicht aber, das er den Zustand nicht wieder verlassen kann, wenn er sich zwischendurch darin befindet.) s₁ ist kein Endzustand; 987 nicht durch 2 teilbar.

Durch Eingabe einer 6 geht der Automat wieder in den Zustand s₂. Endzustand; 9876 ist durch 2 teilbar.

LLAP 🖖

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Inzwischen trudelten einige richtige und fast richtige Lösungen per DM bei mir ein. Mal abwarten, vielleicht machen ja noch ein paar mehr Leute mit?

Wo ihr schon dabei seid, könnt ihr auch gleich weitermachen:

… wenn die dadurch eingegebene Zahl durch 2 teilbar ist.
… wenn die eingegebene Zahl durch 4 teilbar ist.

Was kann denn jetzt wohl kommen?

Die Zusatzaufgabe ist, einen endlichen Automaten zu bauen, der sich nur dann in einem Endzustand befindet, wenn die eingegebene Zahl durch 8 teilbar ist.

LLAP 🖖

[Matthias Apsel]

Hallo Gunnar Bittersmann,

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

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

Bis demnächst
Matthias

[Gunnar Bittersmann]

@@Matthias Apsel

… wenn die eingegebene Zahl durch 8 teilbar ist.

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

Ein Dezimaltrennzeichen gehört nicht zum Eingabe-Alphabet.

Macht nicht der Begriff „Teilbarkeit“ sowieso nur Sinn für ganze Zahlen?

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

LLAP 🖖

[Matthias Apsel]

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

[Gunnar Bittersmann]

@@Matthias Apsel

Gemeint ist Zahl im Dezimalsystem.

Ach so. Nun ja, das Eingabe-Alphabet legt nahe, dass ich das auch meine. 😏

Hexadezimalsystem wäre ja auch zu einfach. 😆

Ich betrachte mich als an 8 gescheitert.

Hm, ich hätte jetzt gedacht, der Gedankenschritt von der 2 zur 4 wäre größer als der von der 4 zur 8. 🤔

LLAP 🖖

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Zum Reim fehlt eine Zeile hier:

Hm, ich hätte jetzt gedacht,
der Gedankenschritt von der 2 zur 4
wäre größer als der von der 4 zur 8. 🤔

LLAP 🖖

[Gunnar Bittersmann]

@@Gunnar Bittersmann

… wenn die dadurch eingegebene Zahl durch 2 teilbar ist.
… wenn die eingegebene Zahl durch 4 teilbar ist.

Was kann denn jetzt wohl kommen?

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

Bei Teilbarkeit durch 2 muss man sich die letzte Stelle ansehen, bei Teilbarkeit durch 4 die letzten beiden, bei Teilbarkeit durch 8 die letzten drei.

Ein regulärer Ausdruck, der durch 8 teilbare Zahlen erkennt:
[048]?[08]|[26]4|[159]6|[37]2 | [0-9]* ( [02468] ([048][08]|[26]4|[159]6|[37]2) | [13579] ([048]4|[26][08]|[159]2|[37]6) )

(Ich hab zur besseren Übersichtlichkeit Leerzeichen gesetzt. Die sind natürlich hier keine Symbole.)

Endlicher Automat: ein Pentakel.

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. 😉)

LLAP 🖖

[dedlfix]

Tach!

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.

dedlfix.

[Gunnar Bittersmann]

@@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 🖖

[dedlfix]

Tach!

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?

Kaputt. Da fehlen die Selbst-Übergänge an allen Zuständen. Und wenn du nun den vom mittleren hinzufügen möchtest, hast du wieder das Symmetrie-Problem.

dedlfix.

[Gunnar Bittersmann]

@@dedlfix

Kaputt. Da fehlen die Selbst-Übergänge an allen Zuständen.

Nix kaputt. Die sind innerhalb der roten Kugeln. 😜

LLAP 🖖

[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.

Da versucht doch tatsächlich jemand, mich auszutricksen! 😈

Naja, der Trick besteht darin, eine Lücke schamlos auszunutzen, die ich in der Aufgabenstellung gelassen hatte und hiermit für diese und alle weiteren Aufgaben schließe: Gesucht ist der minifizierte^[1] Automat, d.h. jener mit der geringsten Anzahl von Zuständen.

LLAP 🖖

---

1. Ich erinnere mich, dass es in der Vorlesung Theoretische Informatik einen Begriff gab, aber nicht mehr genau, welcher. Vielleicht war’s ja wirklich „minifiziert“? Oder „minimal“? ↩︎

[Matthias Apsel]

Hallo Gunnar Bittersmann,

Naja, der Trick besteht darin, eine Lücke schamlos auszunutzen, die ich in der Aufgabenstellung gelassen hatte und hiermit für diese und alle weiten Aufgaben schließe: Gesucht ist der minifizierte[^mini] Automat, d.h. jener mit der geringsten Anzahl von Zuständen.

[^mini]: Ich erinnere mich, dass es in der Vorlesung Theoretische Informatik einen Begriff gab, aber nicht mehr genau, welcher. Vielleicht war’s ja wirklich „minifiziert“? Oder „minimal“?

Ich verwende Minimalautomat.

Allerdings müsstest du auch beweisen, dass sich der Automat nicht um weitere Zustände erleichtern lässt.

Ich würde deshalb von einem Automaten mit möglichst geringer Anzahl von Zuständen sprechen.

Bis demnächst
Matthias

[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. ↩︎

[Matthias Apsel]

Hallo Gunnar Bittersmann,

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

[02468][048] | [13579][26] kann man sich ohne Hilfsmittel gut beim Spazierengehen überlegen.

[0-9]* ist trivial, [048] kommt dann ins Spiel, wenn man die Sonderfälle beachten möchte und den Automaten damit auf drei Zustände reduziert.

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 dafür hatte ich sprechende Zustandsnamen.

die Zustände heißen

• R0 für "Einerziffer hat bei Division durch 4 den Rest 0"
• R2 für "Einerziffer hat bei Division durch 4 den Rest 2"
• U für "Einerziffer ist ungerade"

das Eingabealphabet

• n ∈ N = {0; 4; 8}
• z ∈ Z = {2; 6}
• u ∈ U = {1; 3; 5; 7; 9}

(Grafik erstellt mit FLACI)

Bis demnächst
Matthias

[Gunnar Bittersmann]

@@Matthias Apsel

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

[048] kommt dann ins Spiel, wenn man die Sonderfälle beachten möchte

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

Man kann da ja nicht [0-9]*([02468]?[048]|[13579][26]) schreiben, denn das würde ja alle [0-9]*[048] matchen.

… 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.

(Grafik erstellt mit FLACI)

Ein ziemlich geiles Tool.

Hat mir gute Dienste geleistet zu prüfen, ob @Orlok⁠s oder mein Automat für die Teilbarkeit durch 8 richtig war. Ihr ahnt es: Orloks war’s. 😡

LLAP 🖖

[Matthias Apsel]

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

[Rolf B]

Hallo Matthias,

meiner auch. Bis mir die Redundanzen ins Auge fielen…

Rolf

[Gunnar Bittersmann]

@@Gunnar Bittersmann

BTW, ist auch so ein Kandidat, wo keine fl-Ligatur gesetzt werden sollte.

LLAP 🖖

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Das Bild zeigt einen endlichen Automaten, der sich bei der Eingabe einer Ziffernfolge nur dann im Endzustand (dargestellt durch doppelte Linie) befindet, wenn die dadurch eingegebene Zahl durch 2 teilbar ist. (Führende Nullen sollen erlaubt sein.)

Durch geringfügige Modifikation wird daraus ein Automat, der durch 5 teilbare Zahlen erkennt:

Und einer, der durch 10 teilbare Zahlen erkennt:

Und wenn man einen 2er und einen 10er hinternander setzt, erhält man einen Automaten, der durch 20 teilbare Zahlen erkennt. Hier in der dedlfixschen Gesichtsform:

So, was haben wir denn jetzt? Teilbarkeit durch 2, 4, 5, … Moment, was ist mit der 3?

Hier die Aufgabe für alle, die mit der 8 fertig sind oder mit der 8 fertig sind: 😉

Baue einen endlichen Automaten, der sich nur dann in einem Endzustand befindet, wenn die eingegebene Zahl durch 3 teilbar ist.

Und wenn man den hat, hat man auch durch geringfügige Modifikation den für 6. Und den für 15.

LLAP 🖖

[Rolf B]

Hallo Gunnar,

der für 7 ist auch immer noch offen

Rolf

[Matthias Apsel]

Hallo Rolf B,

der für 7 ist auch immer noch offen

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

Bis demnächst
Matthias

[Gunnar Bittersmann]

@@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 🖖

[Matthias Apsel]

Hallo Gunnar Bittersmann,

Kann man? Ich würde sagen: nein.

Wahrscheinlich war ich zu vorschnell.

Bis demnächst
Matthias

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Wenn man vergisst, dass es Teilbarkeitsregeln gibt

Guter Tip.

kann man alle diese Automaten nach demselben Muster bauen.

Ich hatte mich an den Teilbarkeitsregeln orientiert und von hinten nach vorne gedacht, inbesondere bei den Teilbarkeiten durch 2ⁿ: Was muss die letzte Stelle sein, was die vorletzte, …?

Wenn man aber von vorne nach hinten denkt …

Kann man? Ich würde sagen: nein.

Ich wurde eines besseren belehrt.

Automat, der durch 7 teilbare Zahlen erkennt.

Es trudelten einige Lösungen ein. @Orlok hat besonders viel Liebe reingesteckt:

LLAP 🖖

[dedlfix]

Tach!

So, was haben wir denn jetzt? Teilbarkeit durch 2, 4, 5, … Moment, was ist mit der 3?

Hier die Aufgabe für alle, die mit der 8 fertig sind oder mit der 8 fertig sind: 😉

Baue einen endlichen Automaten, der sich nur dann in einem Endzustand befindet, wenn die eingegebene Zahl durch 3 teilbar ist.

Und wenn man den hat, hat man auch durch geringfügige Modifikation den für 6. Und den für 15.

Vermutlich lassen sich alle diese Automaten nach demselben sehr einfachen Prinzip erstellen. Bei allen Zahlen, die ich probiert haben, gibt es eine Regel, wieviele Knoten es mindestens geben muss. Diese erstellt man und trägt für alle Vielfachen des Teilers bis zum 10-fachen die Verbindungen zum Endzustand ein. Der Rest ist stupide Fleißarbeit beim Ausfüllen der Lücken in der Übergangstabelle. Diese Regeln herauszufinden, überlasse ich vorerst dem geneigten Leser.

So sieht übrigens der 13er Automat aus, und die Automaten werden mit größeren Primzahlen auch nicht mehr kleiner:

dedlfix.

[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.

[Matthias Apsel]

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

[Gunnar Bittersmann]

@@Matthias Apsel

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

So ist die Aufgabe zu verstehen. So sollte die Aufgabe lösbar sein.

nicht aber einen Automaten, der Teilbarkeit durch beliebige n erkennt.

Wie hieß das im Matheunterricht immer: für beliebiges, aber festes n.

LLAP 🖖

[Matthias Apsel]

Hallo Gunnar Bittersmann,

Diese Aufgabe ist nicht lösbar.

Du kannst höchstens für ein konkretes n einen Automaten bauen

So ist die Aufgabe zu verstehen. So sollte die Aufgabe lösbar sein.

Also sind es n Aufgaben. Jede einzelne ist lösbar. Wenn man sich von den Teilbarkeitsregeln löst (wie ich gestern schon schrieb [und bei n < 10 noch ein bisschen aufpassen muss], also war ich doch nicht zu vorschnell).

nicht aber einen Automaten, der Teilbarkeit durch beliebige n erkennt.

Wie hieß das im Matheunterricht immer: für beliebiges, aber festes n.

Genau das geht aber nicht.

Bis demnächst
Matthias

[Gunnar Bittersmann]

@@Matthias Apsel

… also war ich doch nicht zu vorschnell).

… für beliebiges, aber festes n.

Genau das geht aber nicht.

Ich hatte in Anspruch genommen, vorschnell zu sein und zu sagen, dass es für 7 nicht ginge.

Du darfst gern in Anspruch nehmen, vorschnell zu sein und zu sagen, dass es für n nicht ginge. 😉

LLAP 🖖

[Matthias Apsel]

Hallo Gunnar Bittersmann,

Du darfst gern in Anspruch nehmen, vorschnell zu sein und zu sagen, dass es für n nicht ginge. 😉

Das widerspricht dem Prinzip des endlichen Automaten, der endlich heißt wegen der endlich vielen Zustände. Und bei beliebigem n musst du auch beliebig viele Zustände vorhalten.

Bis demnächst
Matthias

[Gunnar Bittersmann]

@@Matthias Apsel

Das widerspricht dem Prinzip des endlichen Automaten, der endlich heißt wegen der endlich vielen Zustände. Und bei beliebigem n musst du auch beliebig viele Zustände vorhalten.

Ich glaube, wir haben eine unterschiedliche Vorstellung davon, was „beliebig“ bedeutet. Du darfst auch gerne „konkret“ dazu sagen (nur dass du halt nicht weißt, welchen konkreten Zahlenwert das n hat).

„Beliebig, aber fest“ heißt: Wähle ein beliebiges n. Erstelle für dieses dann feste (konkrete) n den Automaten, der die Teilbarkeit durch dieses n erkennt.

Dieser Automat braucht nicht beliebig viele Zustände, sondern eine bestimmte Anzahl in Abhängigkeit von n. (Hättest du ein anderes n gewählt, bräuchte der Automat eine andere Anzahl von Zuständen.)

LLAP 🖖

[dedlfix]

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.

[Gunnar Bittersmann]

@@dedlfix

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

Nein.

Meinst du, man bräuchte mehr?

LLAP 🖖

[dedlfix]

Tach!

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

Nein.

Meinst du, man bräuchte mehr?

Nein, ich denke, nach dem Prinzip, das ich (bisher nur) dir per PM in Ausführlichkeit beschrieben habe, sollte sich immer der jeweilige Minimalautomat bauen lassen. Deswegen betrachte ich die "Erstelle für Teiler x"-Aufgaben nur noch als Fleißaufgabe, weil es damit keine Herausforderung mehr ist.

dedlfix.

[MudGuard]

Hi,

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

für 3 komme ich auf 3 Zustände:

                          |         
                          |
                          v
                       ####################
                       #                  # -- 0,3,6,9 -
                       #   x mod 3 = 0    #             |
                       #                  # <-----------
                       ####################
                        /     ^      \    ^
                       /     /        \    \
                    1,4,7   /        2,5,8  \
                     /   2,5,8          \   1,4,7
                    /     /              \    \
                   v     /                v    \
             ---------------             ---------------
 - 0,3,6,9 --|             |-- 2,5,8 --->|             |-- 0,3,6,9 -
|            | x mod 3 = 1 |             | x mod 3 = 2 |            |
 ----------->|             |<-- 1,4,7 ---|             |<-----------
             ---------------             ---------------
             

Kann grad nix hochladen,daher ASCII art. ## für den Endzustand.

cu,
Andreas a/k/a MudGuard

[dedlfix]

Tach!

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

für 3 komme ich auf 3 Zustände:

Wie ist denn die Zahl im Startzustand definiert? Ist sie null oder bereits 0?

dedlfix.

[MudGuard]

Hi,

Wie ist denn die Zahl im Startzustand definiert? Ist sie null oder bereits 0?

ja 😉

cu,
Andreas a/k/a MudGuard

[Rolf B]

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

0,7 -> R5
1,8 -> R6
2,9 -> R0
  3 -> R1
  4 -> R2
  5 -> R3
  6 -> R4

Oder - aus FLACI kopiert, diese Deltafunktion:

 δ  0   1   2   3   4   5   6   7   8   9
R0	R0	R1	R2	R3	R4	R5	R6	R0	R1	R2
R1	R3	R4	R5	R6	R0	R1	R2	R3	R4	R5
R2	R6	R0	R1	R2	R3	R4	R5	R6	R0	R1
R3	R2	R3	R4	R5	R6	R0	R1	R2	R3	R4
R4	R5	R6	R0	R1	R2	R3	R4	R5	R6	R0
R5	R1	R2	R3	R4	R5	R6	R0	R1	R2	R3
R6	R4	R5	R6	R0	R1	R2	R3	R4	R5	R6

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

[Matthias Apsel]

Hallo Rolf B,

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

Ja das passt. Um die Restklassen modulo n zu bestimmen, kannst du so vorgehen: Multipliziere die erste Ziffer mit 10 mod n addiere die zweite. Bilde die Restklasse und fahre fort.

Für n > 10 ist 10 mod n = 10, deshalb hatte es letzte Woche mit dem 7er Automaten nicht funktioniert (Stichwort: vorschnell)

Btw. k ≡ n(mod37) schreibt man k ≡ n(37)

Beispiel bestimme den Rest, den 12345 bei Division durch 119 lässt.

1 × 10 + 2 = 12 ≡ 12(119)
  12 × 10 + 3 = 123 ≡ 4(119)
    4 * 10 + 4 = 44 ≡ 44(119)
      44 * 10 + 5 = 445 ≡ 88(119)

Bis demnächst
Matthias

[Rolf B]

Hallo Matthias,

Btw. k ≡ n(mod37) schreibt man k ≡ n(37)

Ich nicht. Mit Restklassenrechnung bin ich nie wirklich warm geworden, aber wenn ich was drüber gelesen habe, dann immer mit $$a \equiv b \pmod c$$. Unser MathJax hier übrigens auch: Da schrieb ich $$a \equiv b \pmod c$$. Seit wann verwendet wer deine Notation?

Aber dein Verfahren ist dem Augenschein nach anders als meins. Da muss ich mir erstmal überlegen, weshalb das Ergebnis äquivalent ist. Das wird jetzt wieder dauern.

Rolf

[Matthias Apsel]

Hallo Rolf B,

Ich nicht. Mit Restklassenrechnung bin ich nie wirklich warm geworden, aber wenn ich was drüber gelesen habe, dann immer mit $$a \equiv b \pmod c$$. Unser MathJax hier übrigens auch: Da schrieb ich $$a \equiv b \pmod c$$. Seit wann verwendet wer deine Notation?

keine Ahnung, vielleicht ist meine Notation doch nicht korrekt.

Aber dein Verfahren ist dem Augenschein nach anders als meins. Da muss ich mir erstmal überlegen, weshalb das Ergebnis äquivalent ist. Das wird jetzt wieder dauern.

Na so anders ist es doch nicht. Für die 7:

Ermittle den Rest, den 98765 bei Division durch 7 lässt: 10 ≡ 3(7), also muss immer mit 3 multipliziert werden

9 ≡ 2(7)
2 × 3 + 8 = 14 ≡ 0(7)
  0 × 3 + 7 = 7 ≡ 0(7)
    0 × 3 + 6 = 6 ≡ 6(7)
      6 x 3 + 5 = 23 ≡ 2(7)

Bis demnächst
Matthias

[Matthias Apsel]

Hallo Matthias Apsel,

keine Ahnung, vielleicht ist meine Notation doch nicht korrekt.

Puh. https://de.wikipedia.org/wiki/Kongruenz_(Zahlentheorie)#Schreibweise

Bis demnächst
Matthias

[Matthias Apsel]

Hallo Matthias Apsel,

Übrigens, weil 10 ≡ 1(3) und 10 ≡ 1(9) gilt, lauten die Teilbarkeitsregeln für 3 und 9 wie sie eben lauten (Quersumme).

Bis demnächst
Matthias

[Gunnar Bittersmann]

@@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.

1. Ein Automat mit Gedächtnis wäre bspw. ein nichtdeterministischer Kellerautomat, welcher eine kontextfreie Sprache (Typ 2 in der Chomsky-Hierarchie) erkennt.

   Äquivalent dazu: Ein Ausdruck mit „Gedächtnis“ (look-around assertions) ist nicht regulär – auch wenn er fälschlicherweise „regulärer Ausdruck“ genannt wird.

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

$$\left( S, s_{-0}, \Sigma, \delta, F \right) = \left( {s_{-0}, s_0, s_1, \ldots, s_{n-1}}, ;; s_{-0}, ;; {0, 1, \ldots, 9}, ;; \delta(s_u, d) = s_v \text{ mit } v = (10u + d) \bmod n, ;; {s_0} \right)$$

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?

[Gunnar Bittersmann]

@@Gunnar Bittersmann

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.

Ich hätte nicht so vorschnell einen Nachtrag schreiben sollen. Das ist natürlich Unsinn, wie wir am Beispiel mit der 9 (nicht 😉) gesehen haben. Obwohl 9 nicht prim ist, lässt sich der Automat nicht auf weniger als 9 + 1 Zustände reduzieren.

Ich werfe mal eine andere Vermutung in den Raum: Der Automat lässt sich genau dann auf weniger als n + 1 Zustände reduzieren, wenn n durch 2 oder 5 teilbar ist. (Was die Teiler der 10, der Basis unseres Zahlensystems, sind.)

LLAP 🖖

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Ich werfe mal eine andere Vermutung in den Raum: Der Automat lässt sich genau dann auf weniger als n + 1 Zustände reduzieren, wenn n durch 2 oder 5 teilbar ist. (Was die Teiler der 10, der Basis unseres Zahlensystems, sind.)

So sieht’s wohl aus.

Die Übergangstabelle mal am Beispiel für unseren Lieblingsautomaten, den ❤️ 7er:

Die Zeile für s₀ ist eine Kopie der Zeile für s₋₀ wegen δ(s₋₀, d) = δ(s₀, d)

| δ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |---| | s₀ | s₀ | s₁ | s₂ | s₃ | s₄ | s₅ | s₆ | s₀ | s₁ | s₂

und muss im Weiteren nicht betrachtet werden.

| δ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |---| | s₋₀ | s₀ | s₁ | s₂ | s₃ | s₄ | s₅ | s₆ | s₀ | s₁ | s₂ | s₁ | s₃ | s₄ | s₅ | s₆ | s₀ | s₁ | s₂ | s₃ | s₄ | s₅ | s₂ | s₆ | s₀ | s₁ | s₂ | s₃ | s₄ | s₅ | s₆ | s₀ | s₁ | s₃ | s₂ | s₃ | s₄ | s₅ | s₆ | s₀ | s₁ | s₂ | s₃ | s₄ | s₄ | s₅ | s₆ | s₀ | s₁ | s₂ | s₃ | s₄ | s₅ | s₆ | s₀ | s₅ | s₁ | s₂ | s₃ | s₄ | s₅ | s₆ | s₀ | s₁ | s₂ | s₃ | s₆ | s₄ | s₅ | s₆ | s₀ | s₁ | s₂ | s₃ | s₄ | s₅ | s₆

Von δ(s₋₀, 0) ausgehend werden die Felder fortlaufend mit s₀ bis s₆ gefüllt, dann geht’s wieder bei s₀ los u.s.w. u.s.f.

Das gilt auch allgemein für alle n. In einer Zeile sieht’s so aus:

Sei v der Index des Folgezustands für den Zustand sᵤ und die Eingabe d: v = (10u + d) mod n.

Dann gilt für den Index w des Folgezustands für sᵤ und die Eingabe d + 1 (wobei d ≠ 9):
w = (10u + d + 1) mod n = ((10u + d) mod n + 1) mod n = (v + 1) mod n.

w ist also der Nachfolger von v modulo n, d.h. $$w = \begin{cases} v + 1, & \text{wenn } v + 1 < n
0, & \text{sonst} \end{cases}$$

Am Zeilenende sieht’s so aus:

Sei v wieder der Index des Folgezustands für den Zustand sᵤ und die Eingabe 9: v = (10u + 9) mod n.

Dann gilt für den Index w des Folgezustands für sᵤ₊₁ und die Eingabe 0 (wobei u ≠ n − 1):
w = (10(u + 1) + 0) mod n = (10u + 10) mod n = (10u + 9 + 1) mod n = (v + 1) mod n.

Auch hier ist w ist der Nachfolger von v modulo n.

Das heißt: die Tabellenfelder (n Zeilen à 10 Spalten) werden fortlaufend mit s₀ bis $$s_{n-1}$$ gefüllt, dann geht’s wieder bei s₀ los u.s.w. u.s.f. Insgesamt sind es 10 Wiederholungen der Folge s₀, s₁, …, $$s_{n-1}$$.

Wenn nun die Anzahl der Zeilen und die Anzahl der Spalten (also n und 10) teilerfremd sind, kommt in jeder Spalte jeder Index von 0 bis n − 1 genau einmal vor. Es gibt also keine identischen Zeilen, d.h. es können keine Zustände zusammengefasst werden.

Anders hingegen, wenn die Anzahl der Zeilen und die Anzahl der Spalten nicht teilerfremd sind, d.h. wenn n durch 2 oder durch 5 teilbar ist. Bspw. beim 6er:

| δ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |---| | s₋₀ | s₀ | s₁ | s₂ | s₃ | s₄ | s₅ | s₀ | s₁ | s₂ | s₃ | s₁ | s₄ | s₅ | s₀ | s₁ | s₂ | s₃ | s₄ | s₅ | s₀ | s₁ | s₂ | s₂ | s₃ | s₄ | s₅ | s₀ | s₁ | s₂ | s₃ | s₄ | s₅ | s₃ | s₀ | s₁ | s₂ | s₃ | s₄ | s₅ | s₀ | s₁ | s₂ | s₃ | s₄ | s₄ | s₅ | s₀ | s₁ | s₂ | s₃ | s₄ | s₅ | s₀ | s₁ | s₅ | s₂ | s₃ | s₄ | s₅ | s₀ | s₁ | s₂ | s₃ | s₄ | s₅

Die Zeilen für s₋₀ und s₃ sind identisch, ebenso für s₁ und s₄ sowie für s₂ und s₅. Diese Zustände können jeweils zusammengefasst werden – heraus kommt der bekannte Automat mit 4 Zuständen (inclusive s₀):

Auch das gilt allgemein. Wenn n durch 2 teilbar ist, gilt für u < n/2:

$$\delta(s_{u + n/2}, d) = \left(10 \left( u + \tfrac{n}{2} \right) + d \right) \bmod n = \left(10u + 5n + d \right) \bmod n = \left(10u + d \right) \bmod n = \delta(s_u, d)$$

Analog für durch 5 teilbare n und u < ⅘n:

$$\delta(s_{u + n/5}, d) = \left(10 \left( u + \tfrac{n}{5} \right) + d \right) \bmod n = \left(10u + 2n + d \right) \bmod n = \left(10u + d \right) \bmod n = \delta(s_u, d)$$

Damit ist gezeigt, dass der Automat genau dann nicht minimal ist, wenn n durch 2 oder 5 teilbar ist.

LLAP 🖖

[Matthias Apsel]

Hallo Gunnar Bittersmann,

Das passt zusammen mit der Periodizität von Stammbrüchen.

Bis demnächst
Matthias

[Matthias Apsel]

Hallo Matthias Apsel,

Das passt zusammen mit der Periodizität von Stammbrüchen.

vollständig gekürzte Brüche, deren Primfaktorzerlegung des Nenners …

• nur Faktoren 2 oder 5 enthält, haben eine endliche
• nur Faktoren außer 2 und 5 enthält, haben eine sofortperiodische
• beide Sorten von Primfaktoren enthält, haben eine spätperiodische

… Dezimalbruchentwicklung.

Die Länge der Dezimalbruchentwicklung im ersten Fall und die Länge der Vorperiode im dritten Fall ist gleich dem Maximum der Anzahl der Faktoren 2 und 5.

Die Periodenlänge in den Fällen zwei und drei ist gleich der kleinsten Zahl n, für die gilt 10ⁿ ≡ 1(Nenner).

Bis demnächst
Matthias

[Gunnar Bittersmann]

@@Gunnar Bittersmann

… und damit haben wir unseren Automaten:

$$\left( S, s_{-0}, \Sigma, \delta, F \right) = \left( {s_{-0}, s_0, s_1, \ldots, s_{n-1}}, ;; s_{-0}, ;; {0, 1, \ldots, 9}, ;; \delta(s_u, d) = s_v \text{ mit } v = (10u + d) \bmod n, ;; {s_0} \right)$$

FWIW, ich hab das Ding mal in JavaScript implementiert. Na, nicht genau den Automaten, der die Teilbarkeit durch einen (den) Endzustand anzeigt, sondern einen, der bei jeder Eingabe „teilbar“ (W wie wahr) bzw. „nicht teilbar“ (F fie falsch) ausgibt – wie irgendwo in den Untiefen dieses Threads schon mal erwähnt. Da die Ausgabe zu einer Eingabe erfolgt, muss man dann nicht zwischen den Zuständen s₋₀ und s₀ unterscheiden und der Automat kommt mit n Zuständen aus.

$$\begin{align} \text{Zustandsmenge:} &\ S = {s_0, s_1, \ldots, s_{n-1}}
\text{Startzustand:} &\ s_0
\text{Eingabealphabet:} &\ \Sigma = {0, 1, \ldots, 9}
\text{Ausgabealphabet:} &\ \Gamma = {\mathrm W, \mathrm F}
\text{Übergangsfunktion:} &\ \delta(s_u, d) = s_v \text{ mit } v = (10u + d) \bmod n
\text{Ausgabefunktion:} &\ \omega(s_u, d) = \begin{cases} \mathrm W,& \text{wenn } \delta(s_u, d) = s_0, \text{ d.h. wenn } v = (10u + d) \bmod n = 0
\mathrm F,& \text{sonst} \end{cases} \end{align}$$

class DivisibilityFSA
{
	n;
	currentState = 0;
	inputAlphabet = [0,1,2,3,4,5,6,7,8,9];

	constructor(n)
	{
		this.n = n;
	}

	transition = input => this.inputAlphabet.includes(input) ?
		!(this.currentState = (10 * this.currentState + input) % this.n) :
		undefined;
}

In der Kürze liegt die Würze: Eine Zuweisung liefert einen Wert (nämlich den zugewiesenen).
Wenn also für den Index des Folgezustands, d.h. die Restklasse (10 * this.currentState + input) % this.n die falsy 0 rauskommt, wird durch die Negation true zurückgegeben (d.h. „teilbar“).
Kommt ein anderer, ein truthy Wert von 1 bis n − 1 raus, dann false („nicht teilbar“).

Und das nur, wenn die Eingabe aus dem Eingabealphabet ist, ansonsten kommt undefined zurück. Oder wäre null passender?

7er Automat (❤️):

const fsa = new DivisibilityFSA(7);

console.log( fsa.transition(9) ); // false –    9 ist nicht durch 7 teilbar
console.log( fsa.transition(8) ); // true  –   98 ist durch 7 teilbar
console.log( fsa.transition(7) ); // true  –  987 ist durch 7 teilbar
console.log( fsa.transition(6) ); // false – 9876 ist nicht durch 7 teilbar

Mit new DivisibilityFSA(13) schlägt’s dreizehn. Zum Rumspielen

Ich dachte, man könnte currentState und inputAlphabet durch vorangestelltes # privat machen, aber da spielt CodePen nicht mit?

LLAP 🖖

[Doktor Seltsam]

Hallo

Ich dachte, man könnte currentState und inputAlphabet durch vorangestelltes # privat machen, aber da spielt CodePen nicht mit?

Das ist auch keine Standardsyntax. Zumindest noch nicht. Genauso wie die Zuweisungen im Körper deine Klasse. Dabei handelt es sich bislang nur um Proposals, die jederzeit gekippt werden können.

class DivisibilityFSA {

    constructor(n) {
        this.currentState = 0;
        this.inputAlphabet = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
        this.n = n;
    }

    transition(input) {
        if (this.inputAlphabet.includes(input)) {
            return !(this.currentState = (10 * this.currentState + input) % this.n);
        }
    }

}

Eine standardkonforme Implementierung deines Automaten, die nicht erst transpiliert werden muss, könnte so aussehen wie in dem Beispiel oben.

[Gunnar Bittersmann]

@@Doktor Seltsam

Das ist auch keine Standardsyntax. Zumindest noch nicht. Genauso wie die Zuweisungen im Körper deine Klasse. Dabei handelt es sich bislang nur um Proposals, die jederzeit gekippt werden können.

Ah! Ich hätte mal den Text im roten Kasten lesen sollen. Hätte ja was Wichtiges drinstehen können.

    transition(input) {
        if (this.inputAlphabet.includes(input)) {
            return !(this.currentState = (10 * this.currentState + input) % this.n);
        }
    }

Ohne Pfeilfunktion ist das wohl auch leichter lesbar; und den ternären Operator muss man dann auch nicht bemühen.

Dann kann man das auch noch aufdröseln, um deutlich zu machen, dass tatsächlich der Wert der Zuweisung negiert werden soll und dass es sich nicht um einen Schreibfehler handelt (da soll wirklich = stehen, nicht == oder ===):

    transition(input)
    {
        if (this.inputAlphabet.includes(input))
        {
            this.currentState = (10 * this.currentState + input) % this.n;
            return !this.currentState;
        }
    }

LLAP 🖖

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Und wenn man einen 2er und einen 10er hinternander setzt, erhält man einen Automaten, der durch 20 teilbare Zahlen erkennt.

Und wenn man zwei 10er hinternander setzt, erhält man einen Automaten, der durch 100 teilbare Zahlen erkennt. Das Diagramm ersparen wir uns. Wir sind zu höheren Zielen berufen.

Wer wird Millionär?

Die erste Million ist die schwerste.

Das schwerste hieran war wohl, den Startpfeil richtig zu setzen. (Und nicht etwa einen zusätzlichen Startzustand vorzusehen.)

LLAP 🖖

PS: höhere Ziele ≠ hehere Ziele, höhö.

[dedlfix]

Tach!

Und wenn man einen 2er und einen 10er hinternander setzt, erhält man einen Automaten, der durch 20 teilbare Zahlen erkennt.

Und wenn man zwei 10er hinternander setzt, erhält man einen Automaten, der durch 100 teilbare Zahlen erkennt. Das Diagramm ersparen wir uns. Wir sind zu höheren Zielen berufen.

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. Die Frage wäre also, warum das passieren kann. Hängt es mit dem Dezimalsystem zusammen?

Hier mal die komplette Beschreibung "meines" Prinzips:

Für das Prinzip braucht man keine mathematischen Teilungsregeln zu kennen. Der erste Schritt ist, alle Zahlen von 0 bis exklusive 10 × (n + 1) aufzuschreiben, am besten in 10er-Gruppen. Also beim 3er Automaten bis 39, beim 6er bis 69, etc. Dann markiert man sich alle Vielfachen. Man sieht nun, welche 10er nach der 0 nicht markiert sind. Für diese erstellt man Zustände und nummeriert sie von 1 an aufwärts. Den Startzustand benennt man mit 0 und fügt dann noch einen finiten Zustand benannt mit E hinzu. 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. Nun zeichnet man für alle Vielfachen (inklusive 0) bis zum 10-Fachen die Wege zum E ein. Dazu kommen noch die Wege, die von E auf sich selbst zeigen. Das ist auf alle Fälle die 0 und - bei allen n, die kleiner als 10 sind - alle Endziffern von Vielfachen bis zum nächsten Zehner. Also, beim 3er Automaten sind es 0, 3, 6 und 9 wegen 30, 33, 36 und 39, beim 6er sind es die 0 und 6 wegen 60 und 66. Anschließend wechselt man zur Übergangstabelle. Die Zustände sollten von 0 bis E untereinander stehen. Flaci sortiert sie aber nicht natürlich, weswegen Zustände >= 10 nicht richtig platziert sind. Jedenfalls hat man in der ersten Zeile den Zustand 0 (oder Startzustand) und da ist bereits bei Eingabe der Ziffer 0 (obere Reihe) ein E eingetragen. Dann fügt man nur noch aufsteigend mit 1 nach dem E beginnend alle Zustände ein. Wenn keiner mehr übrig ist, geht es mit 0 beginnend weiter. Es sei denn, es steht bereits ein E in dem Feld, dann geht es im darauf folgenden mit 1 weiter. Ist die Zeile voll, setzt man in der nächsten (numerisch aufsteigend) fort bis inklusive E-Zeile. Fertig ist der Automat.

dedlfix.

[Gunnar Bittersmann]

@@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 🖖

[Rolf B]

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

[dedlfix]

Tach!

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

Das hat auch erstmal nicht viel mit Verstehen im wissenschaftlichen Sinne zu tun, sondern war mehr eine Anleitung zum Erstellen der Zustände und dem Ausfüllen der Übergangstabelle im Flaci. Ich habe diese Regelmäßigkeit nicht gefunden, weil ich mathematisch an die Sache rangegangen bin, sondern weil ich Regelmäßigkeiten einerseits optisch in der Exceltabelle für die teilbaren Zahlen (hier am Beispiel der 6)

als auch beim Erstellen der Übergangstabelle gesehen habe.

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

Die Positionen der teilbaren Zahlen wiederholen sich (bei der 6) ab Spalte D.

(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.

Dass die Optimierung am Ende auf dasselbe Ergebnis kommt, wie es unterschiedliche Spaltenmuster gibt, kann kein Zufall sein. Ich habe jedenfalls gesehen, dass die Wiederholung an der ersten Teilbarkeit durch 10 beginnt (jedenfalls bei den von mir untersuchten Zahlen).

dedlfix.

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Der minimale Automat für die Teilbarkeit durch 10ⁿ lässt sich auch einfach formal beschreiben:

$$\begin{align} \text{Menge der Zustände:} \quad S &= {s_0, s_1, \ldots, s_n}
\text{Menge der Endzustände:} \quad F &= {s_n}
\text{Eingabealphabet:} \quad \Sigma &= {0, 1, 2, \ldots, 9}
\end{align}$$

[Ergänzung] Der Index des Zustands gibt die Anzahl der zuletzt in Folge gelesenen Nullen an.

$$\text{Übergangsfunktion:} \quad \delta(s_i, d) = \begin{cases} s_{i+1} & \text{ für } d = 0 \text{ und } i < n
s_n & \text{ für } d = 0 \text{ und } i = n
s_0 & \text{ für } d \ne 0
\end{cases}$$

Das schwerste hieran war wohl, den Startpfeil richtig zu setzen.

$$\text{Startzustand:} \quad s_{n-1}$$

LLAP 🖖

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Das Bild zeigt einen endlichen Automaten, der sich bei der Eingabe einer Ziffernfolge nur dann im Endzustand (dargestellt durch doppelte Linie) befindet, wenn die dadurch eingegebene Zahl durch 2 teilbar ist. (Führende Nullen sollen erlaubt sein.)

Baue einen endlichen Automaten, der sich nur dann in einem Endzustand befindet, wenn die eingegebene Zahl durch 3 teilbar ist.

Man könnte geneigt sein zu denken: Teilbarkeit durch 2 – 2 Zustände, Teilbarkeit durch 3 – 3 Zustände, und kommt auf diesen Automaten:

Na, nicht so ganz. Das leere Wort (keine Eingabe) repräsentiert keine Zahl, die irgendwie teilbar wäre. Der Anfangszustand darf nicht Endzustand sein.

Ich will hier niemanden scharf ankucken; bei der ersten Aufgabe (dem 4er) war auch nicht nur einer zunächst in dasselbe offene Messer gerannt.

Beim 4er (wie auch beim 2er im Bild oben) war der Trick, den Pfeil einfach auf einen anderen passenden Zustand zu setzen. Das funktioniert hier aber nicht, weil keiner passt. Wir müssen s₀ in s₀ und sₑ aufdröseln, die ansonsten identisch „verdrahtet“ sind – nur dass einer Endzustand ist und der andere nicht.

Und wenn man den hat, hat man auch durch geringfügige Modifikation den für 6. Und den für 15.

Teilbarkeit durch 6 heißt Teilbarkeit durch 2 und durch 3. Hier muss man nun nicht Zustände aufdrösen, sondern Übergange, d.h. die Pfeile. Zum Endzustand sₑ führen nur gerade Zahlen als letzte Ziffer (innerer Ring); die ungeraden führen zu einem Zustand, der im Kreis der Teilbarkeit durch 3 eine äquivalente Stelle wie sₑ einnimmt – und einen solchen haben wir schon: das ist ja gerade s₀! (äußerer Ring)

Teilbarkeit durch 15 heißt Teilbarkeit durch 3 und durch 5. Zum Endzustand sₑ führen nur 0 und 5 als letzte Ziffer (innerer Ring); die anderen führen zu s₀ (äußerer Ring):

LLAP 🖖

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Und wenn man den hat …

Analog zum 3er gibt’s auch bei der Teilbarkeit durch 9 einen Ring, in dem man mit 1 in den jeweils nächsten Zustand in eine Richtung (in meinem Diagramm in Uhrzeigerrichtung) kommt und mit 9 − 1 = 8 in die andere. Mit 0 und 9 verbleibt man im jeweiligen Zustand; mit den anderen Ziffern nimmt man Abkürzungen über die Diagonalen:

(Die nahe am Zustand stehenden Symbole geben die Richtung an, wie man aus dem Zustand rauskommt; die Pfeile und doppelten Linien hab ich gespart.)

‚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.)

Das Neuneck mit Diagonalen hatte ich eigentlich für die Teilbarkeit durch 16 angedacht. Es liegt die Vermutung nahe, dass ein Automat dafür 9 Zustände braucht. Allgemein: 2ⁿ⁻¹ + 1 Zustände für die Teilbarkeit durch 2ⁿ.

Da ich faul bin, hatte ich nach einer Grafik eines Neunecks mit Diagonalen gesucht, aber nur eine in einer Auflösung unter 200 × 200 Pixel gefunden. Also selber machen. Da ich faul bin: machen lassen – von einem Script. Und dabei wieder was gelernt: createElement('path') geht nicht; es muss createElementNS('http://www.w3.org/2000/svg', 'path') mit Angabe des SVG-Namensraums sein.

(Neuneck als SVG und als in HTML eingebettetes SVG)

LLAP 🖖

[dedlfix]

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]

@@dedlfix

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.

Oh, schade.

Wenn es mehrere Ebenen gibt, kann man die nicht durch zeichnerische Projektion eliminieren.

Moment, wieso geht nicht?

Einen Schritt zur Seite und es sieht so aus:

LLAP 🖖

[Gunnar Bittersmann]

@@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 🖖

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Das Bild zeigt einen endlichen Automaten, der sich bei der Eingabe einer Ziffernfolge nur dann im Endzustand (dargestellt durch doppelte Linie) befindet, wenn die dadurch eingegebene Zahl durch 2 teilbar ist. (Führende Nullen sollen erlaubt sein.)

Ich mach mal den Columbo: Eine Frage hätte ich da noch. Wie müsste man den Automaten verändern, wenn führende Nullen nicht erlaubt sind?

LLAP 🖖

[dedlfix]

Tach!

Ich mach mal den Columbo: Eine Frage hätte ich da noch. 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 und dort alles auf sich selbst. Die restlichen Übergänge von S0 gehen zu S1.

dedlfix.

[Gunnar Bittersmann]

@@dedlfix

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.

LLAP 🖖

[dedlfix]

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.

[Gunnar Bittersmann]

@@dedlfix

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).

Schon klar. Es ist aber nicht richtig, die alle auf einen Fehler-Zustand zu leiten.

LLAP 🖖

[dedlfix]

Tach!

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).

Schon klar. Es ist aber nicht richtig, die alle auf einen Fehler-Zustand zu leiten.

Wenn "wenn führende Nullen nicht erlaubt sind", dann ist die gesamte Eingabe falsch, wenn sie mit einer führenden 0 beginnt. Wenn führenden Nullen lediglich ignoriert werden sollen, muss die Aufgabenstellung anders lauten.

dedlfix.

[Gunnar Bittersmann]

@@dedlfix

Wenn "wenn führende Nullen nicht erlaubt sind", dann ist die gesamte Eingabe falsch, wenn sie mit einer führenden 0 beginnt.

Eben nicht.

LLAP 🖖

[Rolf B]

Hallo dedlfix,

Worte wie "007" oder "00" wären sicherlich falsch und dürfen nicht auf den Endezustand laufen.

Aber was ist mit... [SPOILER] 😝

Rolf

[Gunnar Bittersmann]

@@Rolf B

Aber was ist mit...

Spielt noch jemand mit? Kann euch dieses Bild zum Weiterspielen motivieren? 😉

Foto: Ralf Roletschek / roletschek.at, CC-BY-SA 3.0

LLAP 🖖

[Matthias Apsel]

Hallo dedlfix,

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).

Hervorhebung von mir.

Wenn "wenn führende Nullen nicht erlaubt sind", dann ist die gesamte Eingabe falsch, wenn sie mit einer führenden 0 beginnt. Wenn führenden Nullen lediglich ignoriert werden sollen, muss die Aufgabenstellung anders lauten.

Nicht alle Zahlen die mit einer Null beginnen, sind ungültig.

Bis demnächst
Matthias

[dedlfix]

Tach!

Nicht alle Zahlen die mit einer Null beginnen, sind ungültig.

Zahlen, die mit 0 beginnen sind Zahlen mit führenden Nullen und die sind nicht erlaubt. "Nicht erlaubt" ist was anderes als "sind zu ignorieren". Erlaubten Zahlen mit nicht erlaubten führende Nullen gibt es nicht, wenn die Eingabe mit 0 anfängt. Wir sind hier in der Informatik, da sind diese Zeichen vorhanden und haben keine Sonderstellung wie beim Rechnen in der Mathematik. Die Aufgabe ist in der Formulierung und mit dem Zusatz nicht lösbar. Es sei denn, ich interpretiere sie anders als nach dem Wortlaut, das wäre dann aber das Fach Deutsch. Und dann ist das Ergebnis nicht mehr deterministisch.

dedlfix.

[Matthias Apsel]

Hallo dedlfix,

Nicht alle Zahlen die mit einer Null beginnen, sind ungültig.

Zahlen, die mit 0 beginnen sind Zahlen mit führenden Nullen und die sind nicht erlaubt.

Und was ist mit 0? Diese Zahl ist durch 2 teilbar. 00 hingegen ist gar keine Zahl, 007 auch nicht.

Bis demnächst
Matthias

[dedlfix]

Tach!

Nicht alle Zahlen die mit einer Null beginnen, sind ungültig.

Zahlen, die mit 0 beginnen sind Zahlen mit führenden Nullen und die sind nicht erlaubt.

Und was ist mit 0? Diese Zahl ist durch 2 teilbar. 00 hingegen ist gar keine Zahl, 007 auch nicht.

Wenn 0 gestattet sein soll, 00 oder noch mehr Nullen aber nicht, ist der Automat nicht erstellbar, weil man (unter anderem) mit 0 und 10 gültigerweise auf den Endzustand kommt, aber dann mit weiteren Nullen nicht unterschiedlich abbiegen kann.

dedlfix.

[Matthias Apsel]

Hallo dedlfix,

Wenn 0 gestattet sein soll, 00 oder noch mehr Nullen aber nicht, ist der Automat nicht erstellbar, weil man (unter anderem) mit 0 und 10 gültigerweise auf den Endzustand kommt, aber dann mit weiteren Nullen nicht unterschiedlich abbiegen kann.

Endliche Automaten dürfen auch mehrere Endzustände haben.

Bis demnächst
Matthias

[Gunnar Bittersmann]

@@Matthias Apsel

Endliche Automaten dürfen auch mehrere Endzustände haben.

Wie schon im Eröffnungsspiel gesagt:

F ⊆ S – Menge der Endzustände, in dem Fall F = {s₂}

Es dürfen sogar alle Zustände Endzustände sein.

Man könnte einen Automaten auch so definieren, dass er beim Übergang von einem Zustand zum nächsten eine Ausgabe tätigt (in dem Fall „teilbar durch n“ bzw. „nicht teilbar durch n“) und alle Zustände Endzustände sind. Dann hätte man auch das Problem des offenen Messers nicht und der Automat käme mit n Zuständen aus.

LLAP 🖖

[dedlfix]

Tach!

Endliche Automaten dürfen auch mehrere Endzustände haben.

Wie schon im Eröffnungsspiel gesagt:

F ⊆ S – Menge der Endzustände, in dem Fall F = {s₂}

Kann ich nicht interpretieren, dazu fehlen mir die Grundlagen.

Es dürfen sogar alle Zustände Endzustände sein.

Dass es mehrere Endzustände geben kann, wusste ich nicht. Grundsätzlich sehe ich das auch nicht als Problem an. Vor allem dann, wenn die Endzustände unterschiedliche Bedeutung haben und die Verarbeitung eben mit unterschiedlichen Ergebnissen enden kann. Mir widerstrebt es aber, das für diese Aufgabenstellung als gültigen Weg anzusehen. Die Aussage zur Teilbarkeit ist ein Datum, das sollte mit einem Zustand abgebildet werden.

dedlfix.

[Rolf B]

Hallo dedlfix,

das sollte mit einem Zustand abgebildet werden.

In trivialen Automaten mag das gelingen.

Wenn's komplizierter wird, dann ist es eben so. Manchmal führen eben mehrere Wege zu verschiedenen Aspekten des gleichen Ziels.

Rolf

[Gunnar Bittersmann]

@@dedlfix

F ⊆ S – Menge der Endzustände, in dem Fall F = {s₂}

Kann ich nicht interpretieren

„Menge“: ein Sack, wo auch mehrere Geschenke reinpassen. 🎅

„der Endzustände“: Genitiv Plural

dazu fehlen mir die Grundlagen.

„Deutsch als Fremdsprache“ in der VHS um die Ecke? SCNR.

Mir widerstrebt es aber, das für diese Aufgabenstellung als gültigen Weg anzusehen. Die Aussage zur Teilbarkeit ist ein Datum, das sollte mit einem Zustand abgebildet werden.

Aufgabenstellung: „Die Aufgabe ist, einen endlichen Automaten zu bauen, der sich nur dann in einem Endzustand befindet, wenn die eingegebene Zahl durch 4 [bzw. n] teilbar ist.“

„In einem Endzustand“ hieß von Anfang an: in einem von mehreren möglichen; ansonsten hätte da ja „im Endzustand“ gestanden.

LLAP 🖖

[Matthias Apsel]

Hallo Gunnar Bittersmann,

F ⊆ S – Menge der Endzustände, in dem Fall F = {s₂}

Kann ich nicht interpretieren

„Menge“: ein Sack, wo auch mehrere Geschenke reinpassen. 🎅

„der Endzustände“: Genitiv Plural

dazu fehlen mir die Grundlagen.

„Deutsch als Fremdsprache“ in der VHS um die Ecke? SCNR.

Ach, Gunnar …

Bis demnächst
Matthias

[Matthias Apsel]

Hallo dedlfix,

Dass es mehrere Endzustände geben kann, wusste ich nicht. Grundsätzlich sehe ich das auch nicht als Problem an. Vor allem dann, wenn die Endzustände unterschiedliche Bedeutung haben und die Verarbeitung eben mit unterschiedlichen Ergebnissen enden kann.

Eine Zahl kann eben aus unterschiedlichen Gründen durch eine andere teilbar sein. Und da ist die Null eben an vielen Stellen eine Diva.

Mir widerstrebt es aber, das für diese Aufgabenstellung als gültigen Weg anzusehen. Die Aussage zur Teilbarkeit ist ein Datum, das sollte mit einem Zustand abgebildet werden.

Die Zustände sind nach außen hin nicht zu sehen. Der Automat befindet sich im Falle der Teilbarkeit am Ende der Eingabe in einem akzeptierenden Zustand. Welcher das ist und wie der Weg dahin war, ist für das Datum Teilbarkeit irrelevant.

Bis demnächst
Matthias

[Rolf B]

Hallo Gunnar,

Örks. 5 Zustände?

Rolf

[Gunnar Bittersmann]

@@Rolf B

Örks. 5 Zustände?

Örks. Wenigstens einer versteht mich. 😉

LLAP 🖖

[Matthias Apsel]

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

[dedlfix]

Tach!

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.

Fehler: zu viele Unbekannte in der Aufgabenstellung. Gemäß welcher Vorschrift ist denn begrenzt, was ein Schüler in Hefte in seinem Besitz schreiben darf?

dedlfix.

[Matthias Apsel]

Hallo dedlfix,

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.

Fehler: zu viele Unbekannte in der Aufgabenstellung. Gemäß welcher Vorschrift ist denn begrenzt, was ein Schüler in Hefte in seinem Besitz schreiben darf?

Das ist nicht begrenzt. Aber wenn ich es exakt beschreiben möchte, ist es schon fast keine Aufgabe mehr.

Bis demnächst
Matthias

[Matthias Apsel]

Hallo Matthias Apsel,

Das ist nicht begrenzt. Aber wenn ich es exakt beschreiben möchte, ist es schon fast keine Aufgabe mehr.

Das Thema scheint ausgelutscht zu sein. Ich führe deshalb mal aus, wie eine Zahl aufgebaut ist.

• sie beginnt mit einem Minuszeichen oder einer Ziffer
• das Minuszeichen darf nur am Anfang vorkommen
• sie hat höchstens ein Komma
• sie darf nicht mit dem Komma enden
• falls sie mit einer Null beginnt, folgt nichts oder ein Komma
• Gunnar hat in seiner an die Jahreszeit angepasste Lösung noch mit Nullen endende Nachkommaanteile verboten

Die Pfeile ins Nirwana führen in den Nebel.

Und ob eine Zahl gültig ist, wird meiner Meinung nach von allen Interpretern auf diese Weise geprüft. Wobei die Kriterien sich durchaus unterscheiden können. In manchen CAS beispielsweise ist 2. eine gültige Zahl und im Unterschied zu 2 ein Näherungswert und das Programm anweist, mit Näherungswerten zu rechnen.

solve(x^2=2.,x) // x=1,414213562373095 or x=-1,414213562373095

solve(x^2=2,x)  // x=√2 or x=-√2

Bis demnächst
Matthias

[Gunnar Bittersmann]

@@Matthias Apsel

Hier sieht man auch schön, wann sich ein Automat nicht reduzieren lässt:

Vom Zustand α links oben (nennen wir ihn „Beteigeuze“) kommt man mit , zum Zustand δ rechts im Gürtel (nennen wir ihn „Mintaka“) und mit − sowie mit 0 bis 9 in den Nebel (aus dem es kein Entkommen mehr gibt).

Vom Zustand β rechts unten (nennen wir ihn „Rigel“) ebenso; es gilt also δ(α, σ) = δ(β, σ) für alle Symbole σ ∈ Σ.

Dennoch kann man die Zustände α und β nicht zu einem zusammenfassen, weil α ein Endzustand ist, β aber nicht.

LLAP 🖖

PS: Ein roter Riese soll ein Endzustand sein? – Da lachen ja die Hühner, äh die Sterngucker.

[Matthias Apsel]

Hallo Gunnar Bittersmann,

Hier sieht man auch schön, wann sich ein Automat nicht reduzieren lässt:

es gilt also δ(α, σ) = δ(β, σ) für alle Symbole σ ∈ Σ.

Dennoch kann man die Zustände α und β nicht zu einem zusammenfassen, weil α ein Endzustand ist, β aber nicht.

Der Automat könnte sich aber trotzdem reduzieren lassen. Schließlich hat er noch andere Zustände.

Bis demnächst
Matthias

[Rolf B]

Hallo Matthias,

warte ein paar Milliarden Jahre, dann reduziert er sich von ganz allein auf ein Black Hole.

Rolf

[Gunnar Bittersmann]

@@Matthias Apsel

Hier sieht man auch schön, wann sich ein Automat nicht reduzieren lässt:

Der Automat könnte sich aber trotzdem reduzieren lassen. Schließlich hat er noch andere Zustände.

Ja, die wären auch jeweils paarweise zu prüfen.

Und wo ich das schon in einer DM erläutert hatte, stelle ich’s auch hier rein.

Schauen wir uns diesen 2er Automaten an:

Von S₁ gelangt man mit 1, 3, 5, 7, 9 zu S₂ und mit 0, 2, 4, 6, 8 zu E.
Von S₂ gelangt man mit 1, 3, 5, 7, 9 zu S₂ und mit 0, 2, 4, 6, 8 zu E.

Beides sind keine Endzustände, deshalb kann man S₁ und S₂ zusammenfassen:

Das o.g. Kriterium allein reicht aber nicht.

Von S₁ gelangt man mit 1, 3, 5, 7, 9 zu S₂ und mit 0, 2, 4, 6, 8 zu E.
Von S₂ gelangt man mit 1, 3, 5, 7, 9 zu S₁ und mit 0, 2, 4, 6, 8 zu E.

Trotzdem kann man auch diesen Automaten genauso reduzieren.

Da müsste ich nochmal drüber nachdenken oder nachlesen (vielleicht hab ich sogar noch meine Unterlagen aus Theoretischer Informatik von der Uni irgendwo im Schrank), wie man das auch noch mit reinbekommt.

Schauen wir uns nochmal den 3er Automaten an:

Von s₀ mit 1, 4, 7 zu s₁, mit 2, 5, 8 zu s₂ und mit 0, 3, 6, 9 zu sₑ.
Von sₑ mit 1, 4, 7 zu s₁, mit 2, 5, 8 zu s₂ und mit 0, 3, 6, 9 zu sₑ.

Stimmt auch überein. Wenn man nun s₀ und sₑ zusammenfassen würde:

Das hatten wir doch schon! 😉

s₀ und sₑ darf man nicht zusammenfassen, da der eine ein Endzustand ist, der andere aber nicht.

LLAP 🖖

[Gunnar Bittersmann]

@@Matthias Apsel

Hallo Gunnar Bittersmann,

Hier sieht man auch schön, wann sich ein Automat nicht reduzieren lässt:

es gilt also δ(α, σ) = δ(β, σ) für alle Symbole σ ∈ Σ.

Dennoch kann man die Zustände α und β nicht zu einem zusammenfassen, weil α ein Endzustand ist, β aber nicht.

Der Automat könnte sich aber trotzdem reduzieren lassen. Schließlich hat er noch andere Zustände.

Zum Beispiel γ rechts oben (nennen wir ihn „Bellatrix“) und den Kopf λ (nennen wir ihn „Heka“): Von beiden geht’s mit 0 zu λ und mit 1 bis 9 zu γ sowie mit − und , in den Nebel. Keine Reduktion, obwohl δ(γ, σ) = δ(λ, σ) für alle Symbole σ ∈ Σ, weil γ ein Endzustand ist, λ aber nicht.

Anders siehts aus, wenn man bei Dezimalbrüchen Nullen am Ende zulässt. (Was ja in der Physik durchaus Sinn macht: 9876,50 ist was anderes als 9876,5 – nämlich eine genauere Messung/Berechnung aus genaueren Messwerten.)

Dann ist λ auch ein Endzustand; γ und λ können zusammengefasst werden. Dazu werden die zu γ führenden Pfeile (von γ selbst und vom rechten Gürtelzustand δ) mit 0–9 beschriftet; λ und alle Pfeile von und zu diesem werden entfernt.

LLAP 🖖

[Gunnar Bittersmann]

@@Matthias Apsel

Ich hab da mal etwas am Fernrohr rumgedreht und das Bild scharfgestellt.

Links das serverseitig auf 400 × 600 Pixel herruntergerechnete Bild <Bild-ID>.png?size=medium. Dateigröße: 31.0 kB.
Rechts das Originalbild <Bild-ID>.png mit 600 × 900 Pixel, im Browser herunterskaliert. Dateigröße: 31.8 kB.

Manchmal macht die Generierung des „medium“-Bildes einfach keinen Sinn. Minimale Einsparung an Dateigröße bei deutlicher Verschlechterung der Qualität.

Lohnt es sich, da etwas Gehirnschmalz reinzustecken, wann man auf das serverseitige Runterrechnen verzichtet und besser gleich das Originalbild ausliefert? @Christian Kruse

LLAP 🖖

[Christian Kruse]

Hallo Gunnar,

Lohnt es sich, da etwas Gehirnschmalz reinzustecken, wann man auf das serverseitige Runterrechnen verzichtet und besser gleich das Originalbild ausliefert? @Christian Kruse

Vor V5 eh nicht. Und danach… warum nicht. Behalts im Kopf 😉

LG,
CK

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Ich mach mal den Columbo: Eine Frage hätte ich da noch. Wie müsste man den Automaten verändern, wenn führende Nullen nicht erlaubt sind?

Wie „ein Sektglas. Passend zum Jahresanfang.“ —@Matthias Apsel

LLAP 🖖

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Ich mach mal den Columbo: Eine Frage hätte ich da noch. Wie müsste man den Automaten verändern, wenn führende Nullen nicht erlaubt sind?

Wie „ein Sektglas. Passend zum Jahresanfang.“ —@Matthias Apsel

Das lässt sich auch verallgemeinern: Wir brauchen in dem allgemeinen Automaten für n zwei zusätzliche Zustände; ich nenne sie mal $$s_{\mathrm{zero}}$$ und $$s_{\mathrm{trap}}$$ (entsprechen ZO und ZF im Fuß von Matthias’ Sektglas), wobei $$s_{\mathrm{zero}}$$ ein weiterer Endzustand ist. Dann ist also

$$\begin{align} S &= {s_{-0}, s_{\mathrm{zero}}, s_{\mathrm{trap}}, s_0, s_1, \ldots, s_n}
F &= {s_{\mathrm{zero}}, s_0} \end{align}$$

(wobei der Startzustand $$s_{-0}$$ dem ZS in Matthias’ Sektglas entspricht).

In der Übergangsfunktion müssen wir den Pfeil für die 0 von $$s_{-0}$$ zu $$s_{\mathrm{zero}}$$ umbiegen (ZS → ZO) und die Ausgänge von $$s_{\mathrm{zero}}$$ und $$s_{\mathrm{trap}}$$ zu $$s_{\mathrm{trap}}$$ (→ ZF) hinzufügen:

$$\delta(s_u, d) = \begin{cases} s_v \text{ mit } v = (10u + d) \bmod n & \text{ für } u = 0, \ldots, 9\text{ sowie für } u = -0 \text{ und } d = 1, \ldots, 9
s_{\mathrm{zero}} & \text{ für } u = -0 \text{ und } d = 0
s_{\mathrm{trap}} & \text{ für } s_u \in {s_{\mathrm{zero}}, s_{\mathrm{trap}}} \end{cases}$$

LLAP 🖖

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Ich möchte mich bei allen Beteiligten für diesen Thread bedanken. Ich hatte anfangs keine Vorstellung, wo dieser hinführen würde.

Ich hab einiges gelernt:

• dass man nicht nur die (Teilbarkeits-)Regeln im Kopf haben, sondern beyond tellerrand denken sollte; dann kann auch vorher Unmöglich-Geglaubtes möglich werden

• dass es für alles Werkzeuge gibt, manchmal auch richtig gute (wie FLACI)

• dass man zum Generieren von SVG-Elementen per JavaScript den Namensraum braucht

• wie man in GeoGebra Körper modelliert (Kugel, Zylinder, Torus)

• dass man mit endlichen Automaten auch Kunst machen kann:

  

LLAP 🖖

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Hier noch mal alle Automaten aus dem Thread gesammelt. Die Bilder verlinken auf die entsprechenden Postings.

Teilbarkeit durch:

 ◀︎ 2            ◀︎ 3            ◀︎ 4

 ◀︎ 5            ◀︎ 6            ◀︎ 7

 ◀︎ 8            ◀︎ 9            ◀︎ 10

 ◀︎ 13            ◀︎ 15            ◀︎ 20

 ◀︎ 1000000           $$\left( {s_{-0}, s_0, \ldots, s_{n-1}}, s_{-0}, {0, \ldots, 9}, \delta(s_u, d) = s_{(10u + d) \bmod n}, {s_0} \right)$$ ◀︎ n

---

ohne führende 0:

 ◀︎ 2           $$\delta(s_u, d) = \begin{cases} s_{v = (10u + d) \bmod n}
s_{\mathrm{zero}}
s_{\mathrm{trap}} \end{cases}$$ ◀︎ n            ◀︎ Dezimalzahl

LLAP 🖖