theoretische Informatik zum Wochenende

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