1
$\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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – Raphael ♦
    Jun 9 '17 at 18:53
1
$\begingroup$

Your idea is right.

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?

Improve this answer
$\endgroup$
-2
$\begingroup$

we known that L is regular.

1w is a concactenation of 1 and w and is regular.(the concatenation of 2 regular language is regular) then w is Necessarily regular. I think. (Wait for the other answers to see)

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – David Richerby
    Jun 9 '17 at 17:34

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.