tail (L) = {y : xy ∈ L for some x ∈ Σ∗} .Show that if L is regular, so is tail (L).

To prove that if L is regular, so is tail(L), we can follow these steps:

1. Assume L is regular. By definition, a language is regular if there exists some finite automaton M that accepts it. Let's say M is the finite automaton that accepts L.

2. We need to construct a finite automaton M' that accepts tail(L).

3. The automaton M' will have the same states, transition function, and final states as M. However, the start state of M' will be different.

4. In M', the start state will be a new state that has ε-transitions (transitions on the empty string) to every state in M. This is because for any string y to be in tail(L), there must exist some string x such that the concatenation xy is in L. By adding ε-transitions from the start state of M' to every state in M, we are effectively allowing for any string x to be "skipped" in the input.

5. Therefore, M' accepts a string if and only if there exists some string x such that the concatenation xy is accepted by M. This is exactly the condition for a string to be in tail(L).

6. Since we have constructed a finite automaton that accepts tail(L), we can conclude that tail(L) is regular.

This completes the proof.