What is $h^{-1}(L)$, for $L$ a regular language and $h$ a homomorphism?

88 Views Asked by At

Let $L = L((00 + 1)^∗)$ and $h : \{a, b\}^* \to \{0, 1\}^*$ be defined by $h(a) = 01$ and $h(b) = 10$. What is $h^{−1}(L)$?

In this context "$+$" means "$\cup$". So the language $L$ is all the words above $\Sigma = \{ 00,1 \}$. Right?

Now, I think I don't understand something fundamental here because take for example $w = 00001 \in L$. What is $h^{-1}(w)?$

1

There are 1 best solutions below

0
On BEST ANSWER

By definition, $h^{-1}(w)$ is the set: $$\{v \in \{a,b\}^* \mid h(v) = w\}$$ Depending on your definitions, this can be an abuse of notation, because $h^{-1}$ might not be a mapping. However, it is convenient to omit the inner braces in the formally more correct $h^{-1}(\{w\})$.

As to the set itself: Because there is no possibility for $h$ to yield three consecutive zeroes, it follows that $h^{-1}(w)$ is empty.

Similarly, there is no possibility for an image of $h$ to have three consecutive ones.

With this information, can you identify the words, if indeed there exist any, that can occur as an image of $h$?

This is the key to the solution; it amounts to describing the set: $$\operatorname{im} h \cap L$$ and subsequently to find its preimage under $h$.