Let L be a regular language. How can I show that the language $\text{Suffix}(L)=\{w \in \Sigma^* \mid \text{ there is a $x \in \Sigma^*$ so that }xw \in L\}$ is also regular? How can I modify the DFA of $L$ so that it accepts $\text{Suffix}(L)$.
Asked
Active
Viewed 142 times
0
-
Do you mean $\text{Suffix}(L) = {w\ |\ \exists x (xw\in L)}$? The way you have defined it above it is just $L$... – universalset Dec 17 '13 at 22:03
-
Yes,that is what I mean... – Mary Star Dec 17 '13 at 22:04
1 Answers
1
The "easy" way to do this is to use the equivalence of NFAs and DFAs. Let the DFA that accepts $L$ be $M$. First, make an NFA $M_s$ whose start state has $\varepsilon$-transitions to every state of $M$ that is accessible from $M$'s start state. (And otherwise $M_s$ has the same states as $M$.) It is not hard to check that $M_s$ accepts Suffix$(L)$. Then one can convert the NFA $M_s$ into a DFA accepting the same language in a canonical way by using the powerset construction.
I'm not sure that there is a simpler direct construction.
universalset
- 8,269
- 20
- 33
-
-
@Rick: There’s been a minor epidemic of them recently. I’m getting hit with a couple on correct answers just about every day. – Brian M. Scott Dec 18 '13 at 21:31
-
@Brian. So I understand from meta. Seems like a bootless protest (if indeed it is) to me. – Rick Decker Dec 19 '13 at 01:31