Versionen dieses Beitrags

Informatik zum Jahresanfang – Auflösung für n

Gb 80x80 Gunnar Bittersmann
  • Informatik zum Jahresanfang – Auflösung für n
  • @@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}$$
  • ~~~JavaScript
  • 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`{:.language-js} die *falsy*{:@en} 0 rauskommt, wird durch die Negation `true`{:.language-js} zurückgegeben (d.h. „teilbar“).
  • Kommt ein anderer, ein *truthy*{:@en} Wert von 1 bis *n* − 1 raus, dann `false`{:.language-js} („nicht teilbar“).
  • Und das nur, wenn die Eingabe aus dem Eingabealphabet ist, ansonsten kommt `undefined`{:.language-js} zurück. Oder wäre `none`{:.language-js} passender?
  • Und das nur, wenn die Eingabe aus dem Eingabealphabet ist, ansonsten kommt `undefined`{:.language-js} zurück. Oder wäre `null`{:.language-js} passender?
  • 7er Automat (❤️):
  • ~~~JavaScript
  • 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)`{:.language-js} schlägt’s dreizehn. [Zum Rumspielen](https://codepen.io/gunnarbittersmann/pen/VqoamX?editors=0011)
  • Ich dachte, man könnte `currentState`{:.language-js} und `inputAlphabet`{:.language-js} durch vorangestelltes `#` privat machen, aber da spielt CodePen nicht mit?
  • LLAP 🖖
  • --
  • *„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“* —Kurt Weidemann

Informatik zum Jahresanfang – Auflösung für n

Gb 80x80 Gunnar Bittersmann
  • Informatik zum Jahresanfang – Auflösung für n
  • @@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}$$
  • ~~~JavaScript
  • 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`{:.language-js} die *falsy*{:@en} 0 rauskommt, wird durch die Negation `true`{:.language-js} zurückgegeben (d.h. „teilbar“).
  • Kommt ein anderer, ein *truthy*{:@en} Wert von 1 bis *n* − 1 raus, dann `false`{:.language-js} („nicht teilbar“).
  • Und das nur, wenn die Eingabe aus dem Eingabealphabet ist, ansonsten kommt `undefined`{:.language-js} zurück. Oder wäre `none`{:.language-js} passender?
  • 7er Automat (❤️):
  • ~~~JavaScript
  • 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)`{:.language-js} schlägt’s dreizehn. [Zum Rumspielen](https://codepen.io/gunnarbittersmann/pen/VqoamX?editors=0011)
  • Ich dachte, man könnte `currentState`{:.language-js} und `inputAlphabet`{:.language-js} durch vorangestelltes `#` privat machen, aber da spielt CodePen nicht mit?
  • LLAP 🖖
  • --
  • *„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“* —Kurt Weidemann