Endliche Automaten und Akzeptoren : Die Lösung erklären?

Question

Ich habe eine Aufgabe und eine Lösung, verstehe aber nicht wie es zu ihr kommt. Kann mir jemand die Lösung erklären?

Aufgabe 12.2 (Aufgaben Winter 2019)
Es sei \( X=\left\{\left(\begin{array}{l}0 \\ 0\end{array}\right),\left(\begin{array}{l}0 \\ 1\end{array}\right),\left(\begin{array}{l}1 \\ 0\end{array}\right),\left(\begin{array}{l}1 \\ 1\end{array}\right)\right\} \) und \( Y=\{0,1\} . \) Ferner seien \( t, b: X^{*} \rightarrow Y^{*} \) die Homomorphismen, die für jedes \( x, y \in Y \) durch \( t\left(\left(\begin{array}{l}x \\ y\end{array}\right)\right)=x \) und \( b\left(\left(\begin{array}{l}x \\ y\end{array}\right)\right)=y \) festgelegt sind. (Siehe Definition von \( f^{* *} \) in Kapitel 8; statt \( t^{* *} \) schreiben wir einfach wieder \( t \) und analog für \( b \).)

a) Geben Sie einen endlichen Automaten \( A_{1} \) mit Eingabealphabet \( X \) und höchstens 4 Zuständen an, sodass \( A_{1} \) genau dann ein Wort \( w \in X^{*} \) akzeptiert, wenn \( \operatorname{Num}_{2}(t(w))>\operatorname{Num}_{2}(b(w)) \) ist.

b) Geben Sie einen endlichen Automaten \( A_{2} \) mit Eingabealphabet \( X \) und höchstens 4 Zuständen an, sodass \( A_{2} \) genau dann ein Wort \( w \in X^{*} \) akzeptiert, wenn \( \operatorname{Num}_{2}(t(w))=2 \cdot \operatorname{Num}_{2}(b(w)) \) ist.

Tipp. Für \( m \in \mathbb{N}_{+} \)gilt \( \operatorname{Repr}_{2}(2 m)=\operatorname{Repr}_{2}(m) \cdot 0\) .

b) Als Abkürzung stehe ∗ für jedes beliebige Symbol aus dem Eingabealphabet X.

Comments

Was ist \(\operatorname{Num}_2\)?

---

Text erkannt:

\( \begin{aligned} \operatorname{num}_{2}(0) &=0 \\ \operatorname{num}_{2}(1) &=1 \\ \operatorname{Num}_{2}(\varepsilon) &=0 \\ \text { sowie } \quad \forall w \in Z_{2}^{*} \forall x \in Z_{2}: \operatorname{Num}_{2}(w x) &=2 \cdot \operatorname{Num}_{2}(w)+\operatorname{num}_{2}(x) \end{aligned} \)
Damit ist dann z. B.
\( \begin{aligned} \operatorname{Num}_{2}(1101) &=2 \cdot \operatorname{Num}_{2}(110)+1 \\ &=2 \cdot\left(2 \cdot \operatorname{Num}_{2}(11)+0\right)+1 \\ &=2 \cdot\left(2 \cdot\left(2 \cdot \operatorname{Num}_{2}(1)+1\right)+0\right)+1 \\ &=2 \cdot(2 \cdot(2 \cdot 1+1)+0)+1 \\ &=2^{3} \cdot 1+2^{2} \cdot 1+2^{1} \cdot 0+2^{0} \cdot 1 \\ &=13 \end{aligned} \)

---

\(\operatorname{num}_{2}(0)=0\)

Ich habe nach \(\operatorname{Num}_2\) gefragt, nicht nach \(\operatorname{num}_2\).

Damit ist dann z. B.

Ich habe nicht nach einem Beispiel gefragt, wie \(\operatorname{Num}_2\) angewendet wird, sondern nach einer Definition von \(\operatorname{Num}_2\).

Die Definition erkennst du daran, dass sie mit den Worten "\(\operatorname{Num}_2\) ist ..." oder "Mit \(\operatorname{Num}_2\) bezeichnen wir ..." oder ähnlichem eingeleitet wird.

---

Wenn ich wüsste, was Num2 ist, könnte ich die Frage selbst lösen.

Die formale Definition:

∀w∈Z2∗∀x∈Z2 : Num2(wx)=2⋅Num2(w)+num2(x)

Ohne zu wissen, was num2 ist, versteht man die formale Definition nicht.