Gunnar Bittersmann: Informatik zum Jahresanfang – Auflösung für n

Beitrag lesen

@@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
0 105

Informatik zum Jahresanfang

Gunnar Bittersmann
  • informatik
  1. 0
    Matthias Apsel
    1. 0
      Gunnar Bittersmann
  2. 0
    Gunnar Bittersmann
  3. 0

    Informatik zum Jahresanfang – Zusatzaufgabe

    Gunnar Bittersmann
    1. 0
      Matthias Apsel
      1. 0
        Gunnar Bittersmann
        1. 0
          Matthias Apsel
          1. 0
            Gunnar Bittersmann
            1. 0
              Gunnar Bittersmann
              • menschelei
    2. 0

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

      Gunnar Bittersmann
      1. 0
        dedlfix
        1. 0
          Gunnar Bittersmann
          1. 0
            dedlfix
            1. 0
              Gunnar Bittersmann
  4. 0
    Gunnar Bittersmann
    1. 0
      Matthias Apsel
  5. 0

    Informatik zum Jahresanfang – Auflösung für 4

    Gunnar Bittersmann
    1. 0
      Matthias Apsel
      1. 0
        Gunnar Bittersmann
        1. 0
          Matthias Apsel
          1. 0
            Rolf B
    2. 0
      Gunnar Bittersmann
      • typografie
  6. 0

    Informatik zum Jahresanfang – noch mehr Teiler

    Gunnar Bittersmann
    1. 0
      Rolf B
      1. 0
        Matthias Apsel
        • informatik
        • mathematik
        1. 0
          Gunnar Bittersmann
          1. 0
            Matthias Apsel
          2. 0

            Informatik zum Jahresanfang – Auflösung für 7

            Gunnar Bittersmann
    2. 0

      Informatik zum Jahresanfang – noch mehr Teiler - Spoiler

      dedlfix
      1. 0
        Gunnar Bittersmann
        1. 0
          Matthias Apsel
          1. 0
            Gunnar Bittersmann
            1. 0
              Matthias Apsel
              1. 0
                Gunnar Bittersmann
                1. 0
                  Matthias Apsel
                  1. 0
                    Gunnar Bittersmann
        2. 0
          dedlfix
          1. 0
            Gunnar Bittersmann
            1. 0
              dedlfix
            2. 0
              MudGuard
              1. 0
                dedlfix
                1. 0
                  MudGuard
        3. 0
          Rolf B
          1. 0
            Matthias Apsel
            1. 0
              Rolf B
              1. 0
                Matthias Apsel
                1. 0
                  Matthias Apsel
            2. 0
              Matthias Apsel
              • mathematik
        4. 0

          Informatik zum Jahresanfang – Auflösung für n

          Gunnar Bittersmann
          1. 0
            Gunnar Bittersmann
            1. 0
              Gunnar Bittersmann
              1. 0
                Matthias Apsel
                • mathematik
                1. 0
                  Matthias Apsel
          2. 0
            Gunnar Bittersmann
            • informatik
            • javascript
            1. 0
              Doktor Seltsam
              1. 0
                Gunnar Bittersmann
    3. 0
      Gunnar Bittersmann
      1. 0
        dedlfix
        1. 0
          Gunnar Bittersmann
        2. 0
          Rolf B
          1. 0
            dedlfix
      2. 0
        Gunnar Bittersmann
    4. 0

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

      Gunnar Bittersmann
      1. 0

        Informatik zum Jahresanfang – Auflösung für 9

        Gunnar Bittersmann
        • informatik
        • javascript
        • svg
        1. 0
          dedlfix
          1. 0
            Gunnar Bittersmann
        2. 0
          Gunnar Bittersmann
  7. 0

    Informatik zum Jahresanfang – noch eine Variation

    Gunnar Bittersmann
    1. 0
      dedlfix
      1. 0
        Gunnar Bittersmann
        1. 0
          dedlfix
          1. 0
            Gunnar Bittersmann
            1. 0
              dedlfix
              1. 0
                Gunnar Bittersmann
              2. 0
                Rolf B
                1. 0
                  Gunnar Bittersmann
              3. 0
                Matthias Apsel
                1. 0
                  dedlfix
                  1. 0
                    Matthias Apsel
                    1. 0
                      dedlfix
                      1. 0
                        Matthias Apsel
                        1. 0
                          Gunnar Bittersmann
                          1. 0
                            dedlfix
                            1. 0
                              Rolf B
                            2. 0
                              Gunnar Bittersmann
                              1. 0
                                Matthias Apsel
                                • menschelei
                            3. 0
                              Matthias Apsel
    2. 0
      Rolf B
      1. 0
        Gunnar Bittersmann
        1. 0
          Matthias Apsel
          1. 0
            dedlfix
            1. 0
              Matthias Apsel
              1. 0
                Matthias Apsel
                1. 0
                  Gunnar Bittersmann
                  1. 0
                    Matthias Apsel
                    1. 0
                      Rolf B
                    2. 0
                      Gunnar Bittersmann
                    3. 0
                      Gunnar Bittersmann
                2. 0
                  Gunnar Bittersmann
                  • bilder
                  • grafik
                  • zu diesem forum
                  1. 0
                    Christian Kruse
    3. 0
      Gunnar Bittersmann
      1. 0
        Gunnar Bittersmann
  8. 2
    Gunnar Bittersmann
  9. 1
    Gunnar Bittersmann