theoretische Informatik zum Wochenende

[Matthias Apsel]

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

[Der Martin]

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

[Matthias Apsel]

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

[Raketengeschichtswissenschaftler]

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.

[Matthias Apsel]

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

[Gunnar Bittersmann]

@@Matthias Apsel

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

Für manche Zahlen gibt es mehrere akzeptable Darstellungen?

LLAP 🖖

[Matthias Apsel]

Hallo Gunnar Bittersmann,

Für manche Zahlen gibt es mehrere akzeptable Darstellungen?

Ich meine, nein.

Bis demnächst
Matthias

[Gunnar Bittersmann]

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

[Matthias Apsel]

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

[Gunnar Bittersmann]

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

[Matthias Apsel]

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

[1unitedpower]

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.

[Rolf B]

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

[Der Martin]

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

[Matthias Apsel]

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

[Rolf B]

Hallo Matthias,

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

Rolf

[Matthias Apsel]

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

[Rolf B]

Hallo Matthias,

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

Rolf

[Matthias Apsel]

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

[Matthias Apsel]

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.

Bis demnächst
Matthias

[Gunnar Bittersmann]

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

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 🖖

[Rolf B]

Hallo Matthias,

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

Rolf

[Gunnar Bittersmann]

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