[es] - Kontekstno slobodni jezici

japan

Član broj: 34328
Poruke: 480
*.dynamic.sbb.rs.

+13 Profil

Kontekstno slobodni jezici - zadatak

^{24.12.2009. u 20:06 - pre 174 meseci}

Imam problem sa jednim zadatkom:

Neka je

(polinom nad N) i

. Dokazati da je

kontekstno slobodan ako i samo ako je

.

Smer <= (kada je imam polinom stepena 1) mi nije problem, to je trivijalno, ali ovaj drugi će mi doći glave.

Odgovor na temu

Goran Rakić
Beograd

Član broj: 999
Poruke: 3766

Sajt: blog.goranrakic.com

+125 Profil

Re: Kontekstno slobodni jezici - zadatak

^{24.12.2009. u 23:49 - pre 174 meseci}

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]}

http://sr.libreoffice.org — slobodan kancelarijski paket, obrada teksta, tablice,
prezentacije, legalno bez troškova licenciranja

Odgovor na temu

Goran Rakić
Beograd

Član broj: 999
Poruke: 3766

Sajt: blog.goranrakic.com

+125 Profil

Re: Kontekstno slobodni jezici - zadatak

^{25.12.2009. u 00:30 - pre 174 meseci}

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

, 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]}

http://sr.libreoffice.org — slobodan kancelarijski paket, obrada teksta, tablice,
prezentacije, legalno bez troškova licenciranja

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
217.65.204.*

+2790 Profil

Re: Kontekstno slobodni jezici - zadatak

^{25.12.2009. u 07:47 - pre 174 meseci}

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

. Tada će takođe za

biti ispunjeno

, pa za

imamo kontradikciju.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

japan

Član broj: 34328
Poruke: 480
*.dynamic.sbb.rs.

+13 Profil

Re: Kontekstno slobodni jezici - zadatak

^{25.12.2009. u 10:11 - pre 174 meseci}

Citat:

Goran Rakić: Dovoljno je pokazati da tvrđenje ne važi za

jer on pripada i klasama višeg stepena.

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.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.telenor.co.yu.

+2790 Profil

Re: Kontekstno slobodni jezici - zadatak

^{25.12.2009. u 11:54 - pre 174 meseci}

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

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

japan

Član broj: 34328
Poruke: 480
*.dynamic.sbb.rs.

+13 Profil

Re: Kontekstno slobodni jezici - zadatak

^{25.12.2009. u 12:19 - pre 174 meseci}

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.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.ptt.rs.

+2790 Profil

Re: Kontekstno slobodni jezici - zadatak

^{25.12.2009. u 18:46 - pre 174 meseci}

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.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Goran Rakić
Beograd

Član broj: 999
Poruke: 3766

Sajt: blog.goranrakic.com

+125 Profil

Re: Kontekstno slobodni jezici - zadatak

^{25.12.2009. u 19:41 - pre 174 meseci}

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

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]}

http://sr.libreoffice.org — slobodan kancelarijski paket, obrada teksta, tablice,
prezentacije, legalno bez troškova licenciranja

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.telenor.rs.

+2790 Profil

Re: Kontekstno slobodni jezici - zadatak

^{25.12.2009. u 21:23 - pre 174 meseci}

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.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu