Koristi se lema o razrastanju za KS jezike (engl. pumping lemma) koja kaže da za svaki KS jezik postoje takvi da se svaka reč može zapisati kao gde da za svako važi .

Dovoljno je pokazati da tvrđenje ne važi za jer on pripada i klasama višeg stepena. Pretpostavljajući da jeste KS, po slučajevima kako sve može da se podeli trebalo bi da dođe do kontradikcije u svakom slučaju.

_{[Ovu poruku je menjao Goran Rakić dana 25.12.2009. u 11:45 GMT+1]}

Zapravo ne gleda se po slučajevima da se broje a-ovi i b-ovi već je dovoljno samo pogledati reč za .

, jer je , a sa druge strane
, jer je

Sledi da reč ne pripada jeziku pa polazna pretpostavka da je on KS nije tačna.

_{[Ovu poruku je menjao Goran Rakić dana 25.12.2009. u 01:40 GMT+1]}

Neka je , dužina pumpanja i . Tada postoje reči takve da je , , i tako da za ma koje važi .

No, tada za svako postoji tako da je , odakle je . Ukoliko je pak polinom stepena bar dva sa pozitivnim vodećim koeficijentom, postojaće takvo da za sve važi , a samim tim i za . Tada će takođe za biti ispunjeno , pa za i imamo kontradikciju.

Ovo je ključna stvar. Ja sam sve vreme pokušavao da dokažem da tvrđenje ne važi za polinom opšteg oblika , što mi nikako nije uspevalo.

Hvala puno.

Pa, dao sam dokaz za opšti polinom stepena bar dva.

Nedeljko, "hvala" je bilo upućeno obojici ;)

Samo sam konstatovao da ne bih imao problem da rešim zadatak da sam uočio da slučaj može da se uopšti.

A ja sam stavio komentar da nije ta činjenica ključna, jer se može pokazati i bez nje. OK, olakšava posao, mada meni i dalje nije jasno kako se opšti slučaj svodi na taj.

Da, izgleda da sam se ja ipak zaleteo. Stepen polinoma traži ne-nula koeficijent uz vodeći član. Moje "rešenje" samo pokazuje da L nije KS za polinome stepena 2 što je uže tvrđenje.

Hajde da pokušam da ispravim, može se posmatrati polinom stepena k.

Dalje po binomnoj formuli .

Za uz dobija se druga nejdnakost potrebna za kontradikciju da je napumpana reč duža od , a kraća od .




_{[Ovu poruku je menjao Goran Rakić dana 25.12.2009. u 21:28 GMT+1]}

Po Lagranževoj teoremi o srednjoj vrednosti je q(n+1)-q(n)=q'(c) za neko c iz intervala (n,n+1). Obzirom da za polinom q stepena bar 2 sa pozitivnim vodećim koeficijentom q'(x) teži beskonačnosti kad x teži beskonačnosti, počev odnekle će biti q'(x)>k, kolika god da je konstanta k, pa skup svih q(n), gde n ide preko N, neće moći da obuhvati nijedan odozgo neograničen aritmetički niz, a po pumpiung lemi bi morao.