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

to zwykły język nad alfabetem . Lewym ilorazem dotyczącym jest język $L$ $\Sigma = \{a,b\}$ $L$ $w \in \Sigma^*$

w^{- 1} L := {v ∣ w v \in L}

$w^{-1} L := \{v \mid wv \in L\}$

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

formal-languages regular-languages closure-properties

— corium
źródło

Odpowiedzi:

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

Teraz to udowodnij.

— Dave Clarke
źródło

w^{-} 1

$w^-1$

L

$L$

w

$w$

(a + b)^{*} (a + b)

$(a+b)^* \;(a+b)$

L

$L$

@corium: Nie wiem, co oznacza twoje ostatnie zdanie.

— Dave Clarke,

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

— StefanH
źródło

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.

Licensed under cc by-sa 3.0 with attribution required.