$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?
12
$\begingroup$
$\endgroup$
migrated from cstheory.stackexchange.com Apr 18 '12 at 0:38
This question came from our site for theoretical computer scientists and researchers in related fields.
14
$\begingroup$
$\endgroup$
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.
answered Apr 18 '12 at 0:46
-
$\begingroup$ it is sufficient to draw a non- deterministic finite state machine which accepting L and $w^-1$ to prove this? $\endgroup$ – corium Apr 18 '12 at 5:25
-
$\begingroup$ @corium: No. You will have to do an abstract proof for arbitrary $L$ and $w$. $\endgroup$ – Raphael♦ Apr 18 '12 at 5:55
-
$\begingroup$ the regular expression $(a+b)^* \;(a+b)$ accept $L$? - or? $\endgroup$ – corium Apr 18 '12 at 18:11
-
$\begingroup$ @corium: I don't know what your last statement means. $\endgroup$ – Dave Clarke Apr 18 '12 at 19:28
1
$\begingroup$
$\endgroup$
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.
