0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

Added2: 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.

$\endgroup$
  • $\begingroup$ So in order to do this, do I need to create an NFA for $L$, then modify it for $L_S$? $\endgroup$ – Jose Aug 16 '13 at 21:45
  • $\begingroup$ @Jose: Yes, that’s one way. You can also work directly with grammars; I’ll add that to my answer. $\endgroup$ – Brian M. Scott Aug 16 '13 at 21:46
  • $\begingroup$ But how do I create the NFA for $L$, since I don't know what $L$ itself is? $\endgroup$ – Jose Aug 16 '13 at 22:01
  • 1
    $\begingroup$ @Jose: There’s no need to do so, or (if you use the other approach) to create a right regular grammar for $L$. What you have to do is prove that the indicated modification of the NFA (or grammar) gives you an NFA that accepts $L_S$ (or a right regular grammar that produces $L_S$). $\endgroup$ – Brian M. Scott Aug 16 '13 at 22:04
  • 1
    $\begingroup$ @Jose: You need to stop thinking in such concrete terms and instead think about how grammars (or NFAs) work. I’ll answer the question at the end of my last comment: you’d have a derivation $S\to X\Rightarrow x$, so your modified grammar would generate the word $x\in L$. $\endgroup$ – Brian M. Scott Aug 17 '13 at 3:24

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.