Informatik zum Jahresanfang – Auflösung für n

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