# Prove a language is regular

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.
• I think you misread the question. The language $L'$ is not $\{1w \mid w \in L\}$. – zarathustra Jun 9 '17 at 14:36