Gunnar Bittersmann: Informatik zum Jahresanfang – noch eine Variation

Beitrag lesen

@@Matthias Apsel

Hier sieht man auch schön, wann sich ein Automat nicht reduzieren lässt:

Der Automat könnte sich aber trotzdem reduzieren lassen. Schließlich hat er noch andere Zustände.

Ja, die wären auch jeweils paarweise zu prüfen.

Und wo ich das schon in einer DM erläutert hatte, stelle ich’s auch hier rein.

Schauen wir uns diesen 2er Automaten an:

Von S₁ gelangt man mit 1, 3, 5, 7, 9 zu S₂ und mit 0, 2, 4, 6, 8 zu E.
Von S₂ gelangt man mit 1, 3, 5, 7, 9 zu S₂ und mit 0, 2, 4, 6, 8 zu E.

Beides sind keine Endzustände, deshalb kann man S₁ und S₂ zusammenfassen:

Das o.g. Kriterium allein reicht aber nicht.

Von S₁ gelangt man mit 1, 3, 5, 7, 9 zu S und mit 0, 2, 4, 6, 8 zu E.
Von S₂ gelangt man mit 1, 3, 5, 7, 9 zu S und mit 0, 2, 4, 6, 8 zu E.

Trotzdem kann man auch diesen Automaten genauso reduzieren.

Da müsste ich nochmal drüber nachdenken oder nachlesen (vielleicht hab ich sogar noch meine Unterlagen aus Theoretischer Informatik von der Uni irgendwo im Schrank), wie man das auch noch mit reinbekommt.

Schauen wir uns nochmal den 3er Automaten an:

Von s₀ mit 1, 4, 7 zu s₁, mit 2, 5, 8 zu s₂ und mit 0, 3, 6, 9 zu sₑ.
Von sₑ mit 1, 4, 7 zu s₁, mit 2, 5, 8 zu s₂ und mit 0, 3, 6, 9 zu sₑ.

Stimmt auch überein. Wenn man nun s₀ und sₑ zusammenfassen würde:

Das hatten wir doch schon! 😉

s₀ und sₑ darf man nicht zusammenfassen, da der eine ein Endzustand ist, der andere aber nicht.

LLAP 🖖

--
„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