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
  • > 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](https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739779#m1739779)). 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](https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740262#m1740262) 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*₁ = 10*z*₀ + *d*₁ ≡ 10*u* + *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* = (10*u* + *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.
  • {:type="i"}
  • {:type="i" role="complementary"}
  • 1. Ein Automat mit Gedächtnis wäre bspw. ein nichtdeterministischer Kellerautomat, welcher eine kontextfreie Sprache (Typ 2 in der [Chomsky-Hierarchie](https://de.wikipedia.org/wiki/Chomsky-Hierarchie)) erkennt.
  • Äquivalent dazu: Ein Ausdruck mit „Gedächtnis“ (*look-around assertions*{:@en}) ist nicht regulär – auch wenn er fälschlicherweise „regulärer Ausdruck“ genannt wird.
  • Damit haben wir unsere Übergangsfunktion *δ*(*sᵤ*, *d*) = *sᵥ* mit *v* = (10*u* + *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](https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740224#m1740224), 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?
  • --
  • *„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
  • > 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](https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739779#m1739779)). 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](https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740262#m1740262) 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*₁ = 10*z*₀ + *d*₁ ≡ 10*u* + *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* = (10*u* + *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.
  • {:type="i"}
  • 1. Ein Automat mit Gedächtnis wäre bspw. ein nichtdeterministischer Kellerautomat, welcher eine kontextfreie Sprache (Typ 2 in der [Chomsky-Hierarchie](https://de.wikipedia.org/wiki/Chomsky-Hierarchie)) erkennt.
  • Äquivalent dazu: Ein Ausdruck mit „Gedächtnis“ (*look-around assertions*{:@en}) ist nicht regulär – auch wenn er fälschlicherweise „regulärer Ausdruck“ genannt wird.
  • Damit haben wir unsere Übergangsfunktion *δ*(*sᵤ*, *d*) = *sᵥ* mit *v* = (10*u* + *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](https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740224#m1740224), 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?
  • --
  • *„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
  • > 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](https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739779#m1739779)). 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](https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740262#m1740262) 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*₋₀ gleich: *δ*(*s*₀, *d*) = *δ*(*s*₋₀, *d*).
  • Außerdem brauchen wir – wie wir am [Beispiel mit der 3](https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740262#m1740262) 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*₁ = 10*z*₀ + *d*₁ ≡ 10*u* + *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* = (10*u* + *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.
  • {:type="i"}
  • 1. Ein Automat mit Gedächtnis wäre bspw. ein nichtdeterministischer Kellerautomat, welcher eine kontextfreie Sprache (Typ 2 in der [Chomsky-Hierarchie](https://de.wikipedia.org/wiki/Chomsky-Hierarchie)) erkennt.
  • Äquivalent dazu: Ein Ausdruck mit „Gedächtnis“ (*look-around assertions*{:@en}) ist nicht regulär – auch wenn er fälschlicherweise „regulärer Ausdruck“ genannt wird.
  • Damit haben wir unsere Übergangsfunktion *δ*(*sᵤ*, *d*) = *sᵥ* mit *v* = (10*u* + *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.
  • --
  • *„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
  • > 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](https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739779#m1739779)). 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](https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740262#m1740262) 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*₋₀ 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*₁ = 10*z*₀ + *d*₁ ≡ 10*u* + *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* = (10*u* + *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.
  • {:type="i"}
  • 1. Ein Automat mit Gedächtnis wäre ein nichtdeterministischer Kellerautomat, welcher eine kontextfreie Sprache (Typ 2 in der [Chomsky-Hierarchie](https://de.wikipedia.org/wiki/Chomsky-Hierarchie)) erkennt.
  • 1. Ein Automat mit Gedächtnis wäre bspw. ein nichtdeterministischer Kellerautomat, welcher eine kontextfreie Sprache (Typ 2 in der [Chomsky-Hierarchie](https://de.wikipedia.org/wiki/Chomsky-Hierarchie)) erkennt.
  • Äquivalent dazu: Ein Ausdruck mit „Gedächtnis“ (*look-around assertions*{:@en}) ist nicht regulär – auch wenn er fälschlicherweise „regulärer Ausdruck“ genannt wird.
  • Damit haben wir unsere Übergangsfunktion *δ*(*sᵤ*, *d*) = *sᵥ* mit *v* = (10*u* + *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.
  • --
  • *„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 – noch mehr Teiler - Spoiler
  • Informatik zum Jahresanfang – Auflösung für n
  • @@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](https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739779#m1739779)). 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](https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740262#m1740262) 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*₋₀ 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*₁ = 10*z*₀ + *d*₁ ≡ 10*u* + *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* = (10*u* + *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.
  • {:type="i"}
  • 1. Ein Automat mit Gedächtnis wäre ein nichtdeterministischer Kellerautomat, welcher eine kontextfreie Sprache (Typ 2 in der [Chomsky-Hierarchie](https://de.wikipedia.org/wiki/Chomsky-Hierarchie)) erkennt.
  • Äquivalent dazu: Ein Ausdruck mit „Gedächtnis“ (*look-around assertions*{:@en}) ist nicht regulär – auch wenn er fälschlicherweise „regulärer Ausdruck“ genannt wird.
  • Damit haben wir unsere Übergangsfunktion *δ*(*sᵤ*, *d*) = *sᵥ* mit *v* = (10*u* + *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.
  • --
  • *„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 – noch mehr Teiler - Spoiler
  • @@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](https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1739779#m1739779)). 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](https://forum.selfhtml.org/self/2019/jan/2/informatik-zum-jahresanfang/1740262#m1740262) 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*₋₀ 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*₁ = 10*z*₀ + *d*₁ ≡ 10*u* + *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* = (10*u* + *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.
  • {:type="i"}
  • 1. Ein Automat mit Gedächtnis wäre ein nichtdeterministischer Kellerautomat, welcher eine kontextfreie Sprache (Typ 2 in der [Chomsky-Hierarchie](https://de.wikipedia.org/wiki/Chomsky-Hierarchie)) erkennt.
  • Äquivalent dazu: Ein Ausdruck mit „Gedächtnis“ (*look-around assertions*{:@en}) ist nicht regulär – auch wenn er fälschlicherweise „regulärer Ausdruck“ genannt wird.
  • Damit haben wir unsere Übergangsfunktion *δ*(*sᵤ*, *d*) = *sᵥ* mit *v* = (10*u* + *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.
  • --
  • *„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“* —Kurt Weidemann