4
$\begingroup$

The exercise is to prove or give a counterexample to the following proposition with $L \subseteq \Gamma^*$ regular and $h: \Gamma \to \Sigma^*$ a homomorphism.

Is there any regular language $L'$ such that $h^{-1}(L^*) = L'^*$ ?

I know that it isn't that easy to see, since $h^{-1}(L^*) \not= h^{-1}(L)^*$ in general with $L = \{a\}$ and $h : \{a,b\} \to \{a\}^*$ with $h(a) = a, h(b) = aa$. It is $h^{-1}(L^*) = \{a,b\}^* \not= \{a\}^* = h^{-1}(L)^*$.

I still fail to deliver a proper argument to prove it.

$\endgroup$
  • 1
    $\begingroup$ We request that you ask only one question per post; this site format doesn't work well when you ask about two different questions in the same post, as you've done here. If you've already answered your own question about (1), it'd be better to remove that entirely from your post; it just adds extra text that readers are in the end supposed to ignore. Can you reformulate exactly what your question is? Also, I confess I'm not sure I understand what your exercise is. I don't know what it means to prove an assumption; if it's an assumption, there's nothing to prove. $\endgroup$ – D.W. Dec 13 '16 at 23:43
  • 1
    $\begingroup$ As far as checking your proof for the first one, we discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. Can you instead ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. Alternatively, is there a single step you're unsure about, and if so, why? $\endgroup$ – D.W. Dec 13 '16 at 23:44
  • $\begingroup$ @D.W. I see your point and since I'm convinced of my proof after checking once more, I removed the first proposition and edited the question to be more precise. $\endgroup$ – PeterMcCoy Dec 14 '16 at 7:00
5
$\begingroup$

Since you solved the first question, let me answer the second one. If you don't mind, I will use $h$ instead of $h'$ for simplicity. Let $L$ be a regular language and let $K = h^{-1}(L^*)$. Since regular languages are closed under inverses of homorphisms, $K$ is regular. Moreover, if $u, v \in h^{-1}(L^*)$, then $h(u), h(v) \in L^*$ and hence $h(uv) = h(u)h(v) \in L^*$. It follows that $uv \in h^{-1}(L^*)$ and thus $K = K^*$. Consequently, $h^{-1}(L^*) = K^*$, which answers your question.

$\endgroup$
  • $\begingroup$ Thank you for the answer, I somehow tried to construct a counterexamples since I thought one of them had to be false and did not think about a direct proof. $\endgroup$ – PeterMcCoy Dec 14 '16 at 7:03

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.