Let $h$ be the homomorphism defined by $$ h(a) = \mathtt{01}, \quad h(b) = \mathtt{10}, \quad h(c) = \mathtt{0}, \quad h(d) = \mathtt{1} $$ and extended to strings in the usual way. Then the inverse function $h^{-1}$ is defined by $$ h^{-1}(w) = \{z\in\{a,b,c,d\}^*\mid h(z)=w\} $$ for any $w\in\{0,1\}^*$. For any such string, define $N(w)=\left|\,h^{-1}(w)\,\right|$, namely the number of strings over $a,b,c,d$ that map to $w$. For example, $N(\mathtt{1100})=2$, since $h(ddcc)=h(dbc)=\mathtt{1100}$ and no other strings map to $\mathtt{1100}$.

Give a recursive definition of $N$. For example, if $w = \mathtt{00}x$ for some string $x$, then $N(\mathtt{00}x) = N(\mathtt{0}x)$, since the first $\mathtt{0}$ in $w$ can only be produced from $c$, not from $a$.

Having done that, compute $N(\mathtt{10100101})$.

  • 4
    $\begingroup$ This looks like a problem dump. Please try to solve the problem yourself first. $\endgroup$ Dec 26, 2015 at 7:54

1 Answer 1


The recurrence relation for $N$ may be defined as $$\begin{align} N(\mathtt{00}x) &= N(\mathtt{0}x)\\ N(\mathtt{01}x) &= N(x)+N(\mathtt{1}x)&\text{from $(a+)\ x$ or $(c+)\ \mathtt{1}x$}\\ N(\mathtt{10}x) &= N(x)+N(\mathtt{0}x)\\ N(\mathtt{11}x) &= N(\mathtt{1}x)\\ N(\mathtt{1}) &= N(\epsilon)&\text{from $(d+)\ \epsilon$}\\ N(\mathtt{0}) &= N(\epsilon)\\ N(\epsilon) &= 1 \end{align}$$

To see this in action, here's what happens when computing $N(\mathtt{0101})$:

enter image description here

You see that $N(\mathtt{0101})=5$, corresponding to the preimages $\{aa, acd, cbd,cda,cdcd\}$. To get $N(\mathtt{10100101})$ we can do the same thing and we find that we wind up with five nodes with values $\mathtt{0101}$ so $N(\mathtt{10100101})=25$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.