-1
$\begingroup$

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

$\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.Schulz
    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$ Nov 26, 2013 at 10:45
  • $\begingroup$ Look for questions involving the quotient operation. $\endgroup$ 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$ Nov 26, 2013 at 18:18

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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