# Given a regular language, show another language is regular

I was hoping someone could help me with this question, since I'm having trouble determining what approach to take.

Let $L \subseteq \{0,1\}^*$ be a regular language. Show the language $\{w \in \{0,1\}^* | 1w \in L\}$ is also regular.

My idea is that whenever we're at the start state to compensate for the lack of the 1, you do an additional transition as if 1 was part of the input and then carry on reading the input as normal.

Since L is regular it has a NFA that accepts it $(Q,\Sigma, \delta, q_0, F)$. Then construct a new NFA $(Q,\Sigma, \delta', q_0, F)$ such that $\delta'(q,a) = \delta(q,a)$ for $q \ne q_0$ and $\delta'(q,a) = \delta(\delta(q,a),1)$ for $q = q_0$

Is this correct?

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– Raphael
Jun 9 '17 at 18:53

However, in general the initial state $q_0$ of a finite state automaton may also be used in other ways than just as a starting position, so the automaton may return to the state. Those later visits do not want to loose the letter $1$.
Are you sure the order $δ(δ(q,a),1)$ is correct?
• The concatenation of two regular languages is regular. However, this does not mean that, just because the concatenation of two languages is regular, the two languages you started with must be regular. For example, let $L$ be any language containing $\varepsilon$ and write $\circ$ for concatenation. Then $\Sigma^*\circ L = \Sigma^*$, which is regular. But you can't conclude that every language containing $\varepsilon$ is regular. Jun 9 '17 at 17:34