0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

This is almost correct. Note however that the given NFA may visit $q_0$ again, in which case you might drop additional 1s. Instead, what about $(Q,\Sigma,\delta, \delta(q_0,1),F)$?

$\endgroup$
  • $\begingroup$ Yes, it did occur to me getting additional 1's could be a problem. However your solution appears to solve that as far as I can tell $\endgroup$ – CrossGuard Jun 9 '17 at 14:49

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.