Inverse image of the image of a formal language and vice versa

52 Views Asked by At

I'm not sure if I've understood inverse images correctly, so I want to ask if my following thoughts are correct:

Suppose, $\Sigma =\{a,b\}$, $L$ and $R$ languages over $\Sigma$ and $h:\Sigma^*\to \Sigma^*$ homomorphism. Is my following argumentation correct?

Let's assume, that we want to disprove the equation $L=h^{-1}(h(L))$ by counter example:
Let $L=\{a,baa\}$ and $h:\Sigma^*\to\Sigma^*$ with $a\mapsto \lambda$ and $baa \mapsto a$. Then, $h(L)= h(\{a,baa\})=\{h(a),h(baa)\}=\{a\}$ and $h^{-1}(h(L))=h^{-1}(a)$ which yields $\{baa\}$ and that is not equal to $L$.

Let's assume, we want to disprove another equation, namely $L=h(h^{-1}(L))$ by counter example:
Let $L,h$ be defined like in the above example. $h^{-1}(L)=\{baa,\emptyset\}$ and $h(\{baa,\emptyset\})=\{a,\emptyset\}$ which is not equal to $L$.

1

There are 1 best solutions below

1
On BEST ANSWER

There are several things that are quite not precise here.

  • Firstly, when you define the morphism $h$, you say that you send $a$ to $\lambda$ (I assume $\lambda$ is the empty word here), and you send $baa$ to $a$. The problem is that $baa$ is not a generator so you cannot quite do that. The problem is that there is a constraint : you have to send $baa$ to $h(b)h(a)h(a)$. But you can send $b$ to whatever you want. Fortunately (you got lucky!) in your example, you can decide to send $b$ on $a$, and then $baa$ will be sent on $a\lambda\lambda = a$.

    To recap this first point, the way you should define $h$ is by saying $a\mapsto \lambda$ and $b\mapsto a$. Any other way is wrong, although you can get lucky and still define something that makes sense. If you define $h$ this way, you can then show, using the fact that it is a morphism, that for any word $w$, $h(w) = aa\ldots a$, where you put as many $a$'s as there were $b$'s in $w$.

  • Secondly, when you compute the preimage $h^{-1}$ of a set $X$, it is defined as the set of all the words $w$ such that $h(w)\in X$, not just one antecedent for each element of $X$. That means for instance that $h^{-1}\{a\}$ contains all the words $w$ such that $h(w) = a$, or in other words, all the words $w$ which contain exactly once the letter $b$. You can start listing them explicitly: $$ h^{-1}\{a\} = \{ b, ab, ba, aab, aba, baa, aaab, \ldots\} $$ You have made the same mistake in the second example. You are right about one thing though, that no word can be sent by $h$ on the word $baa$, since all the images by $h$ only contain the letter $a$. Thus $h^{-1}\{a,baa\} = h^{-1}\{a\}$, and I have described the latter above.

  • Finally, in your post, you wrote $h^{-1}(L) = \{ baa,\emptyset\}$. Besides the fact that you are missing all the other words with just one $b$ (that I have explained already), the $\emptyset$ that you put does not make sense. It is a set of words, and $\emptyset$ is not a word. The correct way to state that noone is sent onto $baa$ is to write $h^{-1}\{ baa \} = \emptyset$, which makes sense. Then you have $h^{-1}\{ a,baa\} = h^{-1}\{a\}\cup h^{-1}\{baa\}$, so you probably wanted to write $\cup\emptyset$. It so happens that $X\cup\emptyset = X$, so you can just forget about this empty set