Comment prouver que les langues régulières sont fermées sous le quotient de gauche?

$L$ est une langue régulière sur l'alphabet . Le quotient gauche de concernant est le langage L w ∈ Σ ∗ w - 1 L : = { v ∣ w v ∈ L $\Sigma = \{a,b\}$$L$$w \in \Sigma^*$

Comment puis-je prouver que est régulier?$w^{-1}L$

Supposons que est une machine déterministe à états finis acceptant L . Introduisez le mot w dans M , ce qui vous amènera dans un état q . Construisez une nouvelle machine M ' qui est la même que M mais a l'état de départ q . Je revendique que M ' accepte w - 1 L .$M$$L$$w$$M$$q$$M'$$M$$q$$M'$$w^{-1}L$

Maintenant, prouve-le.

Un argument très court donne le fameux Théorème de MyHill et Nerode, qui dit qu'un langage est régulier précisément s'il a un nombre fini de quotients. Donc pour et L ⊆ X ∗ nous avons u - 1 ( w - 1 L ) = ( w u ) - 1 L , donc nous avons moins de quotients pour w - 1 L que pour L , en particulier si L juste a un nombre fini de quotients, pour w - $w \in X^{\ast}$$L \subseteq X^{\ast}$$u^{-1}(w^{-1}L) = (wu)^{-1}L$$w^{-1}L$$L$$L$ nous en avons aussi juste un nombre fini.$w^{-1}L$