Jak udowodnić, że zwykłe języki są zamknięte pod lewym ilorazem?

to zwykły język nad alfabetem Σ = { a , b } . Lewym ilorazem L dotyczącym w ∈ Σ ∗ jest język w - 1 L : = { v ∣ w v ∈ L $L$$\Sigma = \{a,b\}$$L$$w \in \Sigma^*$

Jak mogę udowodnić, że jest regularny?$w^{-1}L$

Załóżmy, że jest deterministyczny automat skończony przyjmowania l . Wprowadź słowo w do M , co wyląduje w pewnym stanie q . Zbuduj nową maszynę M ', która jest taka sama jak M, ale ma stan początkowy q . Zastrzeżenia patentowe że M ' przyjmuje w - 1 l .$M$$L$$w$$M$$q$$M'$$M$$q$$M'$$w^{-1}L$

Teraz to udowodnij.

$w \in X^{\ast}$$L \subseteq X^{\ast}$$u^{-1}(w^{-1}L) = (wu)^{-1}L$$w^{-1}L$$L$$L$$w^{-1}L$