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.

  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Nov 6, 2019 at 21:22
  • 1
    $\begingroup$ 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? $\endgroup$
    – ttnick
    Commented Nov 6, 2019 at 21:46

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.