Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $L$ be a regular language, and $\Sigma$ be its alphabet. Then, the language $S(L) = \{y \in \Sigma^*~|~xy \in L \text{ for some string }x \in \Sigma^*\}$ is also regular.

I am trying to demonstrate this by constructing a Non-deterministic Finite Automata for $S(L)$. The solution says to construct epsilon transitions from that start state of a DFA $D$ representing $L$ to the final states of $D$, but I don't understand how that works.

Could someone please clarify what that means? By the way, this is practice, not homework.

share|improve this question
    
Are you sure it said to construct the epsilon transitions from the start state to the final states? What Belgi is proposing seems more likely to have been what was intended. –  Tara B Oct 19 '12 at 21:32

2 Answers 2

up vote 2 down vote accepted

I didn't really think too hard about your book soliton but it seems that for $L=\emptyset$ your book gives that $\epsilon$ is accepted, but $S(L)=\emptyset$.

I will attempt something similar: Consider a finite deterministic automata that accepts $A$.

When is a word in $S(L)$ ? when there is some word $x$ that brings us to a states (from $q_{0}$) and from there $w$ brings as a final state

Where can the word $x$ bring us ? to any reachable state, and note that for every reachable state there is an $x$ (by definition) that can bring us to that state.

So lets build a new automata (non-deterministic with epsilon moves), the automata is the same except we add epsilon moves from $q_{0}$ to any reachable state (formally there will be some difference because we need to go to a set of states ).

Can you see why this works ?

share|improve this answer
    
Thanks! Intuitively, that makes sense. $x$ takes us a state from which we can get to the final state. Hence, we just epsilon transition from the start state to each reachable state. $y$ takes us the rest of the way to a final state. –  John Hoffman Oct 19 '12 at 21:34
    
@JohnHoffman - Yes, this is the idea. –  Belgi Oct 19 '12 at 21:36
    
@belgi I am afraid your answer is incorrect. Take the DFA $1\cdot a = 2$, $2\cdot b = 1$, with $1$ initial and final. It accepts the language $(ab)^*$ but if you add an $\varepsilon$-transition from $1$ to $2$, then the word $b^2$ is accepted, but does not belong to $S(L)$. –  J.-E. Pin Aug 21 '13 at 6:00

This is an instance of a more general result. If $L$ is regular, then for any language $X$ (regular or not), the language $$ X^{-1}L = \bigl\{\ y \in A^* \mid \text{there exists $x \in X$ such that $xy \in L$}\ \bigr\} $$ is regular. This can be proved as follows. First, for each word $x \in A^*$, the language $x^{-1}L$ is regular. Indeed, if $\mathcal{A} = (Q, A, \cdot, i, F)$ is a DFA accepting $L$, then the automaton $(Q, A, \cdot, i.x, F)$ (obtained from $\mathcal{A}$ by changing the initial state $i$ to $i\cdot x$) accepts $x^{-1}L$. It follows that there are only finitely many languages of the form $x^{-1}L$, a (famous) result known as Nerode's lemma. Now observe that $$ X^{-1}L = \bigcup_{x \in X} x^{-1}L $$ but according to Nerode's lemma, this apparently infinite union is a finite one. Therefore $X^{-1}L$ is a finite union of regular sets and hence is regular. In your case, you take $X = A^*$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.