$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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community$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?
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.
A very short argument yields the famous Theorem of MyHill and Nerode, which says that a language is regular precisely iff it has a finite number of quotients. So for $w \in X^{\ast}$ and $L \subseteq X^{\ast}$ we have $u^{-1}(w^{-1}L) = (wu)^{-1}L$, hence we have fewer quotients for $w^{-1}L$ as for $L$, in particular if $L$ just has finitely many quotients, for $w^{-1}L$ we also just have finitely many.