# How to prove regular languages are closed under left quotient?

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

## migrated from cstheory.stackexchange.comApr 18 '12 at 0:38

This question came from our site for theoretical computer scientists and researchers in related fields.

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$.
• it is sufficient to draw a non- deterministic finite state machine which accepting L and $w^-1$ to prove this? – corium Apr 18 '12 at 5:25
• @corium: No. You will have to do an abstract proof for arbitrary $L$ and $w$. – Raphael Apr 18 '12 at 5:55
• the regular expression $(a+b)^* \;(a+b)$ accept $L$? - or? – corium Apr 18 '12 at 18:11
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.