Recurrence for the number of strings defined by a homomorphism

Question

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})$.

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})$:

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