Informatik zum Jahresanfang – Auflösung für n

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