0 Daumen
327 Aufrufe

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.


blob.png

Avatar von

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

blob.png

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community