2
$\begingroup$

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.

  • 0
    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.2012-10-19

2 Answers 2

2

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 ?

  • 0
    To fix the construction, add a new starting state (that can never be reached again) with $\varepsilon$-transitions to all the reachable states2016-07-26
0

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