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.
