12
$\begingroup$

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

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

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.

$\endgroup$
  • $\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$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.