Closure of regular languages under "inverse second half"

Question

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.

Answer 1

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$).