Używanie pompowania lematu w celu udowodnienia, że ​​język

19

Próbuję użyć lematu pompującego, aby udowodnić, że nie jest regularne.L={(01)m2mm0}

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 .Lpw=(01)p2pw=xyz|y|>0|xy|p

Nie jestem pewien, co dalej.

Czy jestem na dobrej drodze? A może jestem daleko?

Momagic
źródło
1
jesteś na dobrej drodze. jeśli „pompujesz”, zmieniasz liczbę zer i 1, ale nie liczbę 2 (dlaczego?). Doprowadzi to do sprzeczności.
Ran G.
och, zauważ, że to nie może być i | x y | < p . To chyba literówka, a miałeś na myśli | y | > 0 . |y|>p|xy|<p|y|>0
Ran G.
1
Zauważ, że pompowanie lematu nie jest tutaj najszybszym sposobem, ponieważ jest bardzo zbliżony do kanonicznych przykładów dla języków nieregularnych. Spróbuj użyć właściwości zamknięcia R E G ! LREG
Raphael
1
Lub sprawdź dowód lematu pompowania, aby zdać sobie sprawę, że możesz mieć pompowaną strunę również pod koniec i pompować 2s, co jest łatwiejsze.
vonbrand,
@vonbrand lub weź odwrotną wersję języka i zastosuj do tego prosty lemat pompowania.
Al.G.

Odpowiedzi:

5

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=xyzxyzxyz=(01)p2p

Oczywiście musisz przejść przez szczegóły i rozważyć wszystkie możliwe podziały.

Dave Clarke
źródło
5

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.xyz=(01)p2p|xy|pxyzyyy

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?012yy

Ponieważ , x y jest całkowicie zawarte w części ( 01 ) p , a z zawiera wszystkie 2 . Więc jeśli powtórzysz y jeszcze raz, otrzymasz dłuższą pierwszą część, ale część 2 p pozostaje taka sama. Innymi słowy, x y y z kończy się dokładnie p literami 2 . Aby poprawnie zakończyć dowód, pokaż, że x y y z zawiera zbyt wiele liter 0 i 1|xy|pxy(01)pz2y2pxyyzp2xyyz01 pasujące do wyrażenia regularnego.

Gilles „SO- przestań być zły”
źródło
4

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)m2mm0}Δ={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:ΣΔ

Σ={a,b}

h(a)=01

h(b)=2

Odwrotny homomorfizm jest:L

h1(L)={anbn|n0}=L

LL

Renato Sanhueza
źródło
3

abcacbc

n(01)1(01)2(01)n+1(01)p(01)qpq(01)p2p(01)q2pL

Louis
źródło