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

-- „Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“ —Kurt Weidemann

Folgende Nachrichten verweisen auf diesen Beitrag:

freiwillige Angabe, für jeden sichtbar
freiwillige Angabe, für jeden sichtbar
freiwillige Angabe, für jeden sichtbar

Vorschau (Nachricht wird im Forum „SELF-Forum“ erscheinen)

  • Keine Tag-Vorschläge verfügbar
  • keine Tags vergeben

abbrechen

0105

Informatik zum Jahresanfang

  1. 0
    1. 0
  2. 0
  3. 0

    Informatik zum Jahresanfang – Zusatzaufgabe

    1. 0
      1. 0
        1. 0
          1. 0
            1. 0
    2. 0

      Informatik zum Jahresanfang – Auflösung der Zusatzaufgabe für 8

      1. 0
        1. 0
          1. 0
            1. 0
  4. 0
    1. 0
  5. 0

    Informatik zum Jahresanfang – Auflösung für 4

    1. 0
      1. 0
        1. 0
          1. 0
    2. 0
  6. 0

    Informatik zum Jahresanfang – noch mehr Teiler

    1. 0
      1. 0
        1. 0
          1. 0
          2. 0

            Informatik zum Jahresanfang – Auflösung für 7

    2. 0

      Informatik zum Jahresanfang – noch mehr Teiler - Spoiler

      1. 0
        1. 0
          1. 0
            1. 0
              1. 0
                1. 0
                  1. 0
        2. 0
          1. 0
            1. 0
            2. 0
              1. 0
                1. 0
        3. 0
          1. 0
            1. 0
              1. 0
                1. 0
            2. 0
        4. 0

          Informatik zum Jahresanfang – Auflösung für n

          1. 0
            1. 0
              1. 0
                1. 0
          2. 0
            1. 0
              1. 0
    3. 0
      1. 0
        1. 0
        2. 0
          1. 0
      2. 0
    4. 0

      Informatik zum Jahresanfang – Auflösung für 3, 6 und 15

      1. 0

        Informatik zum Jahresanfang – Auflösung für 9

        1. 0
          1. 0
        2. 0
  7. 0

    Informatik zum Jahresanfang – noch eine Variation

    1. 0
      1. 0
        1. 0
          1. 0
            1. 0
              1. 0
              2. 0
                1. 0
              3. 0
                1. 0
                  1. 0
                    1. 0
                      1. 0
                        1. 0
                          1. 0
                            1. 0
                            2. 0
                              1. 0
                            3. 0
    2. 0
      1. 0
        1. 0
          1. 0
            1. 0
              1. 0
                1. 0
                  1. 0
                    1. 0
                    2. 0
                    3. 0
                2. 0
                  1. 0
    3. 0
      1. 0
  8. 2
  9. 1