Given a regular language L on the input alphabet Σ, and X a subset of Σ*, show that the language {$w$:$w$ $\epsilon$ L, there is a x $\epsilon$ X so that $wx$ $\epsilon$ L} is also regular. Could you help me showing this, because I got stuck..
Asked
Active
Viewed 58 times
0
-
Just out of curiosity, where did you get stuck? I admit, this one does sound pretty tricky. – Dennis Meng Dec 11 '13 at 21:30
1 Answers
1
HINT: Let $M$ be a DFA for $L$. $M'$, will be a DFA for the new language. It will be exactly the same as $M$ except for its set of acceptor states. A state $q$ should be an acceptor state in $M'$ if and only if it has an $x$-transition for some $x\in X$ to a state that is ... ?
When I say that $M$ and $M'$ have an $x$-transition from a state $q$ to a state $q'$, I mean that that if the machine is in state $q$ and reads the input word $x$, it ends up in state $q'$. If you’re familiar with the extended transition function $\delta^*$, I mean that $\delta^*(q,x)=q'$.
Brian M. Scott
- 616,228
-
...if and only if it has an x-transition for some x∈X to a state that is an acceptor state in $M$. Is this right? – Mary Star Dec 11 '13 at 21:52
-
1
-
-
1