Matthias Apsel: theoretische Informatik zum Wochenende

Hallo alle,

vor einiger Zeit hatten wir es schon einmal mit endlichen Automaten zu tun. Da ging es um die Teilbarkeit.

Heute lautet die Aufgabe: Konstruiere einen endlichen Automaten über dem Alphabet {I, …, M}, der alle Zeichenfolgen akzeptiert, die gültigen römischen Zahlen entsprechen.

Bis demnächst
Matthias

--
Du kannst das Projekt SELFHTML unterstützen,
indem du bei Amazon-Einkäufen Amazon smile (Was ist das?) nutzt.
  1. Hallo Matthias,

    Heute lautet die Aufgabe: Konstruiere einen endlichen Automaten über dem Alphabet {I, …, M}, der alle Zeichenfolgen akzeptiert, die gültigen römischen Zahlen entsprechen.

    gehen wir davon aus, dass römische Zahlen auf Zifferblättern von Uhren immer gültig sind? Da wird die 4 nämlich gern als IIII geschrieben; nach der reinen Lehre müsste es aber IV sein.

    Ich weiß nicht, wie weit dieses Detail für die Lösung relevant ist, ich wollte es nur erwähnt haben.

    Ciao,
     Martin

    --
    Nein, ich bin kein Klugscheißer. Ich weiß es wirklich besser.
    1. Hallo Der Martin,

      gehen wir davon aus, dass römische Zahlen auf Zifferblättern von Uhren immer gültig sind? Da wird die 4 nämlich gern als IIII geschrieben;

      Das hat in der Neuzeit – soweit ich weiß – den Grund, dass man dadurch immer eine durch 4 teilbare Anzahl der Zeichen hat. Bei der Herstellung vieler Uhren blieb nichts übrig.

      I
      II
      III
      IIII
      V
      VI
      VII
      VIII
      IX
      X
      XI
      XII

      4 × X
      4 × V
      20 × I

      Außerdem steht "IV" für "JU" und damit Jupiter. Und Jupiter Namen oder Kürzel durfte man ganz früher nur in zeremoniellen Zusammenhängen schreiben.

      nach der reinen Lehre müsste es aber IV sein.

      Ja.

      Ich weiß nicht, wie weit dieses Detail für die Lösung relevant ist, ich wollte es nur erwähnt haben.

      Das ist relevant. Also die Zahlen nach der reinen Lehre.

      Bis demnächst
      Matthias

      --
      Du kannst das Projekt SELFHTML unterstützen,
      indem du bei Amazon-Einkäufen Amazon smile (Was ist das?) nutzt.
  2. die gültigen römischen Zahlen entsprechen

    Das verlangt nach einer Definition von "römischen Zahlen".

    Denn das rein additive 'VIIII' (9) war z.B. durchaus gültig - bis sich die zu einer kürzeren Schreibweise ('IX', ebenfalls 9) führende Substraktionsregel im Mittelalter(sic!) durchsetzte.

    Zudem wären da noch die Symbole für Zahlen von 1.000 bis 1.000.000 Mio, die ebenfalls recht spät gebräuchlich wurden und gar nicht zu "Automaten über dem Alphabet {I, …, M}" passen. Was ist übrigens mit dem C, dem D, dem V, dem X??

    Ich hatte mich mal dem römischen Zahlensystem befasst. Hier die (ganz praktischen) (PHP-)Funktionen.

    1. Hallo Raketengeschichtswissenschaftler,

      Das verlangt nach einer Definition von "römischen Zahlen".

      • höchstens drei gleiche Zeichen aufeinander folgend
      • Subtraktionsregel des Mittelalters
      • I, V, X, L, C, D, M

      Bis demnächst
      Matthias

      --
      Du kannst das Projekt SELFHTML unterstützen,
      indem du bei Amazon-Einkäufen Amazon smile (Was ist das?) nutzt.
  3. @@Matthias Apsel

    der alle Zeichenfolgen akzeptiert, die gültigen römischen Zahlen entsprechen.

    Für manche Zahlen gibt es mehrere akzeptable Darstellungen?

    LLAP 🖖

    --
    „Man kann sich halt nicht sicher sein“, sagt der Mann auf der Straße, „dass in einer Gruppe Flüchtlinge nicht auch Arschlöcher sind.“
    „Stimmt wohl“, sagt das Känguru, „aber immerhin kann man sich sicher sein, dass in einer Gruppe Rassisten nur Arschlöcher sind.“

    —Marc-Uwe Kling
    1. Hallo Gunnar Bittersmann,

      Für manche Zahlen gibt es mehrere akzeptable Darstellungen?

      Ich meine, nein.

      Bis demnächst
      Matthias

      --
      Du kannst das Projekt SELFHTML unterstützen,
      indem du bei Amazon-Einkäufen Amazon smile (Was ist das?) nutzt.
      1. @@Matthias Apsel

        Für manche Zahlen gibt es mehrere akzeptable Darstellungen?

        Ich meine, nein.

        Welche soll dann die akzeptable sein? Die kürzest mögliche, bspw. IL?

        LLAP 🖖

        --
        „Man kann sich halt nicht sicher sein“, sagt der Mann auf der Straße, „dass in einer Gruppe Flüchtlinge nicht auch Arschlöcher sind.“
        „Stimmt wohl“, sagt das Känguru, „aber immerhin kann man sich sicher sein, dass in einer Gruppe Rassisten nur Arschlöcher sind.“

        —Marc-Uwe Kling
        1. Hallo Gunnar Bittersmann,

          Welche soll dann die akzeptable sein? Die kürzest mögliche, bspw. IL?

          Die richtige. IL ist nicht gültig.

          I darf nur von V oder X subtrahiert werden.
          X darf nur von L oder C subtrahiert werden.
          C darf nur von D oder M subtrahiert werden.

          XLIX wäre also richtig.

          Bis demnächst
          Matthias

          --
          Du kannst das Projekt SELFHTML unterstützen,
          indem du bei Amazon-Einkäufen Amazon smile (Was ist das?) nutzt.
          1. @@Matthias Apsel

            Welche soll dann die akzeptable sein? Die kürzest mögliche, bspw. IL?

            Die richtige. IL ist nicht gültig.

            Ist das so? Ich bilde mir ein, damals auch schon mal MIM gesehen zu haben. 1999 ist aber schon ’ne Weile her …

            I darf nur von V oder X subtrahiert werden.
            X darf nur von L oder C subtrahiert werden.
            C darf nur von D oder M subtrahiert werden.

            Das dürfte die Aufgabe einfacher machen.

            LLAP 🖖

            --
            „Man kann sich halt nicht sicher sein“, sagt der Mann auf der Straße, „dass in einer Gruppe Flüchtlinge nicht auch Arschlöcher sind.“
            „Stimmt wohl“, sagt das Känguru, „aber immerhin kann man sich sicher sein, dass in einer Gruppe Rassisten nur Arschlöcher sind.“

            —Marc-Uwe Kling
  4. Hallo Matthias Apsel,

    Ich bekam einen Hinweis per Mail:

    Heute lautet die Aufgabe: Konstruiere einen endlichen Automaten über dem Alphabet {I, …, M}, der alle Zeichenfolgen akzeptiert, die gültigen römischen Zahlen entsprechen.

    Heute lautet die Aufgabe: Konstruiere einen endlichen Automaten über dem Alphabet {I, …, M}, der nur die Zeichenfolgen akzeptiert, die gültigen römischen Zahlen entsprechen.

    Bis demnächst
    Matthias

    --
    Du kannst das Projekt SELFHTML unterstützen,
    indem du bei Amazon-Einkäufen Amazon smile (Was ist das?) nutzt.
    1. Heute lautet die Aufgabe: Konstruiere einen endlichen Automaten über dem Alphabet {I, …, M}, der alle Zeichenfolgen akzeptiert, die gültigen römischen Zahlen entsprechen.

      Heute lautet die Aufgabe: Konstruiere einen endlichen Automaten über dem Alphabet {I, …, M}, der nur die Zeichenfolgen akzeptiert, die gültigen römischen Zahlen entsprechen.

      Jetzt provozierst du mich aber.

      $$\mathcal{A}_1 = (\{q_0\}, \Sigma, \delta, \{q0\})$$
      $$\mathcal{A}_2 = (\{q_0\}, \Sigma, \delta, \emptyset)$$
      wobei $$ \delta(q_0,\sigma) = q_0\ \forall \sigma \in \Sigma$$

      $$\mathcal{A}_1$$ akzeptiert alle Zeichenfolgen, die gültigen römischen Zeichen entsprechen. Das heißt, wenn es sich bei einem Wort um ein römisches Numeral handlet, dann wird es von $$\mathcal{A}_1$$ akzeptiert.

      $$\mathcal{A}_2$$ akzeptiert nur Zeichenfolgen, die gültigen römischen Zeichen entsprechen. Das heißt, wenn $$\mathcal{A}_2$$ ein Wort akzeptiert, dann ist es römisches Numeral.

      Gesucht ist $$\mathcal{A_3}$$, der genau die römischen Numerale akzeptiert.

  5. Hallo Matthias,

    die Angabe { I, ..., M } suggeriert eine Teilmenge der ASCII Zeichen von I bis M, also IJKLM. Aber das meinst Du offenbar nicht. Du meinst die explizit aufzuzählende Menge { I, V, X, L, C, D, M }, richtig?

    Rolf

    --
    sumpsi - posui - clusi
    1. Hallo,

      die Angabe { I, ..., M } suggeriert eine Teilmenge der ASCII Zeichen von I bis M, also IJKLM. Aber das meinst Du offenbar nicht. Du meinst die explizit aufzuzählende Menge { I, V, X, L, C, D, M }, richtig?

      im Kontext römischer Zahlen bzw. der Buchstaben, mit denen sie dargestellt werden, habe ich das von Anfang an angenommen - besser gesagt, ich bin gar nicht auf die Idee gekommen, dass man die Beschreibung auch anders verstehen könnte.

      Ciao,
       Martin

      --
      Ich stamme aus Ironien, einem Land am sarkastischen Ozean.
    2. Hallo Rolf B,

      die Angabe { I, ..., M } suggeriert eine Teilmenge der ASCII Zeichen von I bis M, also IJKLM. Aber das meinst Du offenbar nicht. Du meinst die explizit aufzuzählende Menge { I, V, X, L, C, D, M }, richtig?

      Richtig.

      Bis demnächst
      Matthias

      --
      Du kannst das Projekt SELFHTML unterstützen,
      indem du bei Amazon-Einkäufen Amazon smile (Was ist das?) nutzt.
      1. Hallo Matthias,

        noch eine Rückfrage. Muss der endliche Automat deterministisch sein?

        Rolf

        --
        sumpsi - posui - clusi
        1. Hallo Rolf B,

          noch eine Rückfrage. Muss der endliche Automat deterministisch sein?

          Hm. Man kann ja jeden NEA in einen DEA umwandeln. Ich hatte tatsächlich einen DEA im Sinn. Aber ich würde mich auch über einen NEA freuen.

          Bis demnächst
          Matthias

          --
          Du kannst das Projekt SELFHTML unterstützen,
          indem du bei Amazon-Einkäufen Amazon smile (Was ist das?) nutzt.
          1. Hallo Matthias,

            ein NEA wäre noch überschaubar. Aber ein DEA sieht nach einer verkanteten Katastrophenzone aus...

            Rolf

            --
            sumpsi - posui - clusi
            1. Hallo Rolf B,

              ein NEA wäre noch überschaubar. Aber ein DEA sieht nach einer verkanteten Katastrophenzone aus...

              Vielleicht sollte ich mich mit dem regulären Ausdruck zufriedengeben …

              Bis demnächst
              Matthias

              --
              Du kannst das Projekt SELFHTML unterstützen,
              indem du bei Amazon-Einkäufen Amazon smile (Was ist das?) nutzt.
  6. Hallo alle,

    Heute lautet die Aufgabe: Konstruiere einen endlichen Automaten über dem Alphabet {I, …, M}, der alle Zeichenfolgen akzeptiert, die gültigen römischen Zahlen entsprechen.

    Es gibt zwei Teilnehmer, @Gunnar Bittersmann und @Rolf B. Rolf verlinkte auf https://www.hsg-kl.de/faecher/inf/material/sprachen/roemisch/index.php und Gunnar hat Frühstücksbrettchen gemalt.

    DEA, der genau die römischen Zahlen akzeptiert

    Bis demnächst
    Matthias

    --
    Du kannst das Projekt SELFHTML unterstützen,
    indem du bei Amazon-Einkäufen Amazon smile (Was ist das?) nutzt.
    1. @@Matthias Apsel

      Gunnar hat Frühstücksbrettchen gemalt.

      So dachte ich erst. Dann hab ich meine Zeichnung mal eine Vierteldrehung nach links gedreht und gesehen: es ist eine Matrjoschka.

      DEA, der genau die römischen Zahlen akzeptiert

      Ergänzung (nicht eingemalt): Alle Zustände außer dem Startzustand sind Endzustände.

      DM, LC und VX stehen für D,M, L,C bzw. V,X.

      LLAP 🖖

      --
      „Man kann sich halt nicht sicher sein“, sagt der Mann auf der Straße, „dass in einer Gruppe Flüchtlinge nicht auch Arschlöcher sind.“
      „Stimmt wohl“, sagt das Känguru, „aber immerhin kann man sich sicher sein, dass in einer Gruppe Rassisten nur Arschlöcher sind.“

      —Marc-Uwe Kling
    2. Hallo Matthias,

      naja, teilgenommen habe ich nicht wirklich. Ich habe angesichts der Komplexität aufgegeben und das mitgeteilt...

      Rolf

      --
      sumpsi - posui - clusi
    3. @@Matthias Apsel

      Rolf verlinkte auf https://www.hsg-kl.de/faecher/inf/material/sprachen/roemisch/index.php

      Finde ich ziemlich unbrauchbar. Bei der Anornung der Zustände des DFA im Kreis ist keinerlei Struktur erkennbar. Außerdem ist oftmals nicht zu erkennen, welche Beschriftung zu welchem Pfeil gehört.

      Der DFA hat ebenso wie meiner 19 Zustände; ich nehme mal an, dass sie übereinstimmen. Die Übergänge hab ich nicht geprüft; geht ja aus o.g. Grund gar nicht, da bräuchte man die Matrix.

      Der NFA ist Quatsch, glaube ich. An den Pfeilen müssen Symbole stehen; II, III, IV usw. sind keine Symbole.

      Ich hab einen NFA mal angefangen, aber noch nicht komplett aufgemalt. So wie ich das sehe, hat der auch 19 Zustände.

      LLAP 🖖

      --
      „Man kann sich halt nicht sicher sein“, sagt der Mann auf der Straße, „dass in einer Gruppe Flüchtlinge nicht auch Arschlöcher sind.“
      „Stimmt wohl“, sagt das Känguru, „aber immerhin kann man sich sicher sein, dass in einer Gruppe Rassisten nur Arschlöcher sind.“

      —Marc-Uwe Kling