HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Inverse Homomorphisms and Kleene star

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
inversestarhomomorphismsandkleene

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#67382, answer score: 5

Revisions (0)

No revisions yet.