# Closure of regular languages under “inverse second half”

Theorem. Show that if $$L$$ is regular, then so is $$\varphi(L)=\left\{w \in \Sigma^{*} \mid \text {there exists an } \alpha \in \Sigma^{*} \text { with }|\alpha|=|w| \text { and } \alpha w \in L\right\}$$ Proof. Let $$L$$ be a regular language. Because $$L$$ is regular, there exists a DFA $$M$$ that accepts it. We construct out of $$M$$ a $$\lambda$$NFA $$M'$$ whose language is $$\varphi(L)$$.

We can think of a computation of $$M$$ as moving a token across the states of $$M$$. The machine $$M'$$ will reuse the states of $$M$$, but will use three tokens: white, red and blue. Initially, the blue token is put on $$q_0$$ (the initial state of $$M$$), and the white and red tokens are put on a nondeterministically guessed state (both tokens on the same state).

1. Describe the transitions of $$M'$$.
2. Describe the acceptance condition of $$M'$$.

Could someone please help me with that? I research regular expressions, DFAs, NFAs, and conversions between all of theses, but I still don't know how to solve this question.

• We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Nov 6 '19 at 21:22
• This question is still oddly formatted. Why did you put everything in \$\$ + \text?! This ist still an exercise question. What have you tried so far to solve it? – ttnick Nov 6 '19 at 21:46

The white token is a placeholder, which just remembers the original state of the red token (of course, the roles of these two tokens can be switched); this is the state at which $$M$$ would be after reading $$\alpha$$. The red token corresponds to the $$w$$ part of the word, and the blue token to its $$\alpha$$ part.
When reading a symbol, the red token advances according to the rules of $$M$$, the white token stays put, and the blue token guesses a symbol and advances according to the rules of $$M$$ (in effect, it guesses one symbol of $$\alpha$$).
The machine accepts if the blue and white tokens are at the same state (so we guessed correctly the state at which $$M$$ is after reading $$\alpha$$), and the red token is at an accepting state of $$M$$ (so $$\alpha w \in L$$).