Question

Let L ⊆ Σ ∗ and define S(L), the suffix-language of L, as S(L) = {w ∈ Σ ∗ | x = yw for some x ∈ L, y ∈ Σ ∗ } Show that if L is regular, then S(L) is also regular.

Answer 1

If L is regular, then there is a DFA that accepts L. This DFA has an initial state q₀.

Construct an NFA that is the same as the DFA, except it has a new initial state q_-1 with an outgoing lambda transition to q₀ and every other state that is reachable from q₀.

The NFA accepts S(L), therefore S(L) is regular.

Explanation:

In plain language, S(L) is the set of strings that the strings of L end with. That is, every string in L is also in S(L), and so are all of the suffixes of L.

This means that we can transform the finite state machine that accepts L into one that accepts S(L) by providing a way to jump to every arbitrary initial part of the processing, and to let the last part of a string find the accepting state as normal. The given construction does this. To prove it, you would show that S(L) is equal to the language accepted by the NFA by showing that each is a subset of the other, as follows:

If x = yw is an element of L, then the string y would leave the DFA in some particular state. In the NFA, there is a lambda-transition from the initial state to this particular state, so processing the string w from this state will land the NFA in an accepting state by following the same path as the DFA.

Conversely, if w is any string accepted by the NFA, that means that it followed one of the lambda transitions from the initial state and then followed the same path as the DFA. Since these lambda transitions only go to reachable states of DFA, there is some string y that would put the DFA in that state. Since x = yw is accepted by the DFA, that means w is an element of S(L).

.... Please like the answer........ And comment if any query....... Thanks