nicht angemeldet
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 🖖
„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“ —Kurt Weidemann
Matthias Apsel
Rolf B
MudGuard