0

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.

Julian
  • 1,401
  • The pumping lemma is useful for showing that things are not regular. To show that something is regular, you should construct a finite-state machine or regular expression that accepts it. As a hint, you should try to modify a machine for $L_1$ into a machine for $L_2$. – Jalex Stark May 05 '18 at 11:01
  • Thanks! I also thought about that, but I don't even know what the machine for $L_1$ would look like, right? – Julian May 05 '18 at 11:14
  • Is it correct to assume the definition of $L_2$ is supposed to read $L_2 = {\phi(z)|z\in L_1}$? – Samasambo May 05 '18 at 12:11
  • Yes, thank you! – Julian May 05 '18 at 12:14

1 Answers1

1

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.

Samasambo
  • 351