Show that $L_2 = \{\phi(z) | z \in L_2\}$ is a regular language

27 Views Asked by At

Assume that $L_1$ is a regular language over the alphabet $\Sigma$. The function $\phi: \Sigma^* \rightarrow \Sigma^*$ cancels every second symbol, so for example $\phi(z_1z_2z_3z_4) = z_1z_3.$ Show that $L_2 = \{\phi(z) | z \in L_1\}$ is regular too.

After a couple of attempts, I figured out that it might be the best course of action to use the pumping lemma here. So, we know that every regular language fullfills the pumping lemma. So by assuming that $L_2$ wouldn't be regular, we would further assume that the pumping lemma doesn't hold, so that there is a word $z = uvw \in L_2$ that doesn't hold for all the conditions (which can be seen here https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement).

Unfortunately, I don't know where to go from here.

1

There are 1 best solutions below

0
On

Think abstractly about what an FA (finite automaton) would look like for $L_1$. What if you "collapsed" into the start state all of the states that the start state leads to? By collapsed, I mean that if $S_0$ is the start state, and for example $S_0$ leads to $S_1$ and $S_2$, then you could add to $S_0$ every transition that $S_1$ and $S_2$ have, and remove $S_1$ and $S_2$. You could do the same thing now for the next layer i.e. collapse the states that take 3 transitions to get to in the FA for $L_1$ into the states that take 2 transitions to get to. And so on, thus accounting for the removal of every second symbol.

This idea is not fully fleshed out (how do you deal with collapsing accept states; what if the state 3 symbols away is for example the start state), so you would need to fill in the details.