Given that $L\subseteq\{0, 1\}^*$ is a regular language, how can I show that the language $L' =\{ w \in \{0, 1\}^∗ \mid 1w \in L \}$ is also regular?

The exercise asks me to provide a formal account of any construction used in your argument

My thoughts were to introduce two DFAs respectively for $L$ and $L'$ and then define components of $L'$.

Define the DFA $D = ( Q, E, g, q_0, F)$ for regular language $L$ where

  • $Q$ is a set of states
  • $E$ is the alphabet
  • $g$ is the transition function
  • $q_0$ is the start state
  • $F$ is the set of accept states

and define the DFA $D' = (Q', E', g', q'_0, F')$ for the language $L'$.

The main issue now is to define the components of $D'$.

Any help would be much appreciated, thanks.


The DFA $D'$ looks like $D$ with $g'(q'_0,1)=q_0$ and $g'(q'_0,0)=\hat q$, where $\hat q$ is a new state not in $D$. Then $D'$ should behave as $D$ when 1 is read as the first symbol.

  • $\begingroup$ I think you misread the question. The language $L'$ is not $\{1w \mid w \in L\}$. $\endgroup$ – zarathustra Jun 9 '17 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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