Próbuję użyć lematu pompującego, aby udowodnić, że nie jest regularne.
Oto co mam do tej pory: Załóżmy, że jest regularne i niech p będzie długością pompowania, więc w = ( 01 ) p 2 p . Rozważ każdy rozkład pompowania w = x y z taki, że | y | > 0 i | x y | ≤ p .
Nie jestem pewien, co dalej.
Czy jestem na dobrej drodze? A może jestem daleko?
Odpowiedzi:
Wskazówka: Musisz rozważyć, jak wyglądają wszystkie dekompozycje , więc jakie są wszystkie możliwe rzeczy x , y i z, że x y z = ( 01 ) p 2 p . Następnie pompujesz każdy z nich i sprawdzasz, czy dostajesz sprzeczność, która będzie słowem nie w twoim języku. Każdy przypadek musi prowadzić do sprzeczności, która byłaby wówczas sprzecznością z pompującym lematem. Voila! Język nie byłby regularny.w = x yz x y z x yz= ( 01 )p2)p
Oczywiście musisz przejść przez szczegóły i rozważyć wszystkie możliwe podziały.
źródło
Masz rozkład i ograniczenie długości | x y | ≤ p . Co nam to mówi o tym, jak x , y i z zmieści się w rozkładzie? W szczególności lemat pompowania pozwala ci powtarzać y , więc twoim celem jest znalezienie sposobu, w jaki wielokrotne powtarzanie y (lub usuwanie y , czasem jest to prostsze) nieodwracalnie zaburzy wzór, który definiuje język.x yz= ( 01 )p2)p | xy| ≤p x y z y y y
Wzór ma oczywistą granicę: pierwsza część zawiera powtórzenia , druga część zawiera tylko 2 . Interesujące jest to, gdzie y spada. Czy y zawsze jest zawarty w jednej z tych części, czy też może obejmować obie te części?01 2 y y
źródło
Trzy lata później udowodnimy, że przy Δ = { 0 , 1 , 2 } nie jest regularne z powodu sprzeczności przy użyciu właściwości zamknięcia (sposób szybszy niż przy użyciu lematu pompującego ).L={(01)m2m∣m≥0} Δ={0,1,2}
Najpierw przypuszczamy, że jest regularne. Wiemy, że zwykłe języki są zamknięte pod wpływem odwrotnego homomorfizmu.L
Rozważ homomorfizm z:h:Σ∗→Δ∗
Odwrotny homomorfizm jest:L
źródło
źródło