Problem Detail: $L$ is a regular language over the alphabet $Sigma = {a,b}$. The left quotient of $L$ regarding $w in Sigma^*$ is the language $$w^{-1} L := {v mid wv in L}$$ How can I prove that $w^{-1}L$ is regular?
Asked By : corium
Answered By : Dave Clarke
Assume $M$ is a deterministic finite state machine accepting $L$. Feed the word $w$ into $M$, which will land you in some state $q$. Construct a new machine $M'$ which is the same as $M$ but has start state $q$. I claim that $M'$ accepts $w^{-1}L$. Now prove it.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1326
