$L$ is a regular language and $w$ is any word, not necessarily in $L$. We define the set as
$$L/w = \{x \in \Sigma ^* \mid xw \in L\}.$$
Show that $L/w$ is regular.
I'm really struggling with this one. I know its going to come on my final next week.
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Maybe it is easier to argue with the reflected version of $L$. Do you know that regular languages are closed under reflection? Then argue with the DEA for this language. $\endgroup$– A.SchulzCommented Nov 26, 2013 at 9:57
-
$\begingroup$ It seems that you peeked at the final, since you already know two questions that are going to appear there. $\endgroup$– Yuval FilmusCommented Nov 26, 2013 at 10:45
-
$\begingroup$ Look for questions involving the quotient operation. $\endgroup$– Hendrik JanCommented Nov 26, 2013 at 17:11
-
$\begingroup$ Thanks guys. He gave us a list of 15 possible questions that 'could' be on it and these were the two toughest ones so I assume they will be on it. $\endgroup$– StevenRidlayCommented Nov 26, 2013 at 18:18
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Hint: Consider a DFA for $L$. Suppose that upon reading $x$, the DFA is at state $s$. Can you predict at which the DFA would be after reading $xw$?
answered Nov 26, 2013 at 10:44