Need help with this regular language proof

Question

I'm trying to prove that if $L$ is regular, then $L_S$ is regular as well.

$L_s$ = {$x$ | $∃$ $w ∈ Σ^*$ such that $wx∈L$}

I know one way to do this would be to create an NFA that accepts $L$, then modify it so it accepts $L_S$ as well.

Answer 1

Try adding $\epsilon$-transitions from the initial state to each acceptor state.

Added: If you prefer, you can start with a right regular grammar for $L$, with initial symbol $S$, and add productions $S\to X$ for each non-terminal symbol $X$.

Added₂: Since $L$ is regular, it can be generated by a right regular grammar $G=\langle N,\Sigma,P,S\rangle$. It’s well-known that we may without loss of generality assume that $S$ does not appear on the righthand side of any production in $P$, and that every non-terminal other than $S$ does occur on the righthand side of some derivation in $G'$.

Let $G'=\langle N,\Sigma,P',S\rangle$, where $P'=P\cup\big\{S\to X:X\in N\setminus\{S\}\big\}$; in other words, $G'$ is the same as $G$, except that we’ve added a production $S\to X$ for each non-terminal symbol $X$ other than $S$ itself. $G'$ is clearly an extended right regular grammar, so it generates a regular language. We’re done if we can prove that $G'$ generates the language $L_S$. To do this, we must prove two things:

1. if $x\in L_S$, then $G'$ generates $x$; and
2. if $G'$ generates $x$, then $x\in L_S$.

Suppose, then, that $x\in L_S$. By definition this means that there is a $w\in\Sigma^*$ such that $wx\in L$, and that means that there is a derivation $S\Rightarrow^* wx$ in $G$. Since $G$ is right regular, the symbols of $wx$ are generated from left to right during the derivation. That is, if $wx=\sigma_1\sigma_2\ldots\sigma_n$, the derivation must have the form

$$S\Rightarrow\sigma_1X_1\Rightarrow\sigma_1\sigma_2X_2\Rightarrow\ldots\Rightarrow\sigma_1\sigma_2\ldots\sigma_{n-1}X_{n-1}\Rightarrow\sigma_1\sigma_2\ldots\sigma_{n-1}\sigma_nX_n\Rightarrow\sigma_1\sigma_2\ldots\sigma_{n-1}\sigma_n\;,$$

where $X_1,\dots,X_n$ are non-terminal symbols, not necessarily distinct. Thus, at some stage of the derivation we must have a word of the form $wX$ for some non-terminal $X$, and the derivation therefore must have the form $S\Rightarrow^* wX\Rightarrow^* wx$, and we can see that $X\Rightarrow^* x$. That is, $G$ allows us to generate the word $x$ if we get to start with the non-terminal $X$. $G'$ has a production $S\to X$, and it also has all of the productions of $G$ that are used in the $G$-derivation $X\Rightarrow^* x$, so in $G'$ we can form the derivation $S\Rightarrow X\Rightarrow^* x$; this shows that $G'$ generates $x$.

Now suppose that $G'$ generates $x$, meaning that there is a $G'$-derivation $S\Rightarrow^* x$. The productions in $P'$ with $S$ on the lefthand side have one of the following forms: $S\to\epsilon$; $S\to\sigma$ for some $\sigma\in\Sigma$; $S\to\sigma X$ for some $\sigma\in\Sigma$ and $X\in N$; or $S\to X$ for some $X\in N$. Thus, the derivation of $x$ must begin $S\Rightarrow\epsilon$, $S\Rightarrow\sigma$ for some $\sigma\in\Sigma$, $S\Rightarrow\sigma X$ for some $\sigma\in\Sigma$ and $X\in N$, or $S\Rightarrow X$ for some $X\in N$.

• Suppose that it begins $S\Rightarrow\epsilon$ or $S\Rightarrow\sigma$; then that is the whole derivation, so $x\in L\subseteq L_S$.
• Suppose that it has the form $S\Rightarrow\sigma X\Rightarrow^*\sigma y=x$, where $X\Rightarrow^*y$. The hypotheses on $G$ ensure that the $G'$-derivation $X\Rightarrow^*y$ uses only productions in $P$, so it’s a $G$-derivation. The production $S\to\sigma X$ is also in $P$, so the entire derivation $S\Rightarrow x$ is a $G$-derivation, and $x\in L\subseteq L_S$.
• Suppose that it has the form $S\Rightarrow X\Rightarrow^* x$; the hypotheses on $G$ ensure that the $G'$-derivation $X\Rightarrow^* x$ is also a $G$-derivation: it uses none of the new productions in $P'\setminus P$. By hypothesis $X$ appears on the righthand side of some $G$-derivation, i.e., there is a $w\in\Sigma^*$ such that in $G$ we have a derivation $S\Rightarrow^* wX$. Combining this with the $G$-derivation $X\Rightarrow^* x$, we get a $G$-derivation $S\Rightarrow^*wX\Rightarrow^*wx$. Clearly $w\in\Sigma^*$ and $wx\in L$, so $x\in L_S$.

In all cases, therefore, $x\in $L_S$, and the proof is complete.