Let $h$ be a homomorphism and let $L$ be a language. Writing ${}^*$ for Kleene star, I want to show that $(h^{-1}(L))^* \neq h^{-1}(L^*)$. Can I prove this just by showing that we can have $h^{-1}(L)$ to be empty (because no strings are mapping into $L$) and therefore the right side is the empty set? Doing the same to the left side gives $\emptyset^* = \{\epsilon\}\neq\emptyset$.

  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – D.W. Oct 7 '15 at 23:47
  • 2
    $\begingroup$ I'm not sure what you mean by "we can have $h^{−1}(x)$ which does not have a map in $L$". Could you try to explain? $\endgroup$ – David Richerby Oct 8 '15 at 14:16

Unfortunately both sides contain the empty string. As you say, the Kleene star of the empty set also contains the empty string: $\varnothing^* = \{ \lambda\}$. The Kleene star of a language $L$, equals $L^* = \cup_{i\ge 0} L^i$, where $L^0 = \{\lambda\}$ and $L^i = L \cdot L^{i-1}$ for $i\ge 1$.

On the other hand $h(\lambda) = \lambda$ for any morphism $h$, so $\lambda \in h^{-1}(K)$ whenever $\lambda \in K$. As $L^*$ contains the empty string this is the case here.

However, this does not mean the two sets are equal. Consider $h:\{a,b\}^*\to \{a\}^*$ defined by $h(a) = a$ and $h(b) = aa$ and $L=\{a\}$.

| cite | improve this answer | |
  • $\begingroup$ Thanks, So now it seems, that sets are equal. So we use proof that left-side is subset of right-side and right-side of let-side. We will divide the cases into a) empty word b) word of u1....un where ui does belong to set L. A) would be proofed just by definition of Kleene. and b would use the definition of homomrphism that shows h(1).h(n) = h(1n) and we will use this to show that one is subset of another. Is it right ? $\endgroup$ – POC Oct 8 '15 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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