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


2 Answers 2


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.

  • $\begingroup$ it is sufficient to draw a non- deterministic finite state machine which accepting L and $w^-1$ to prove this? $\endgroup$
    – corium
    Commented Apr 18, 2012 at 5:25
  • $\begingroup$ @corium: No. You will have to do an abstract proof for arbitrary $L$ and $w$. $\endgroup$
    – Raphael
    Commented Apr 18, 2012 at 5:55
  • $\begingroup$ the regular expression $(a+b)^* \;(a+b)$ accept $L$? - or? $\endgroup$
    – corium
    Commented Apr 18, 2012 at 18:11
  • $\begingroup$ @corium: I don't know what your last statement means. $\endgroup$ Commented Apr 18, 2012 at 19:28

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.


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.