Kontekstno slobodni jezici - zadatak

Kontekstno slobodni jezici - zadatak 24.12.2009. u 21:06 · pre 205 meseci #1

Imam problem sa jednim zadatkom:

Neka je $p \in \textbf{N}[x]$ (polinom nad N) i $\textbf{L}=\{a^n b^{p(n)} | n \ge 1 \}$ . Dokazati da je $\textbf{L}$ kontekstno slobodan ako i samo ako je $deg(p) < 2$ .

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

Re: Kontekstno slobodni jezici - zadatak 25.12.2009. u 00:49 · pre 205 meseci #2

Koristi se lema o razrastanju za KS jezike (engl. pumping lemma) koja kaže da za svaki KS jezik $L$ postoje $p,q > 0$ takvi da se svaka reč $z \in L, |z| > p$ može zapisati kao $uvwxy$ gde $|vx| > 0, |vwx|<q$ da za svako $k > 1$ važi $uv^kwx^ky \in L$ .

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

Potpis

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

Re: Kontekstno slobodni jezici - zadatak 25.12.2009. u 01:30 · pre 205 meseci #3

Zapravo ne gleda se po slučajevima da se broje a-ovi i b-ovi već je dovoljno samo pogledati reč $a^nb^{n^2} \in \textbf{L}$ za $n > p,q$ .

$|uv^2wx^2y| > |uvwxy| = |a^nb^{n^2}|$ , jer je $|vx| > 0$ , a sa druge strane
$|uv^2wx^2y| \le |uvwxy| + |vwx| < (n+n^2) + n < (n+1) + (n+1)^2 = |a^{n+1}b^{(n+1)^2}|$ , jer je $|vwx| \le q < n$

Sledi da reč $|uv^2wx^2y|$ ne pripada jeziku $\textbf{L}$ pa polazna pretpostavka da je on KS nije tačna.

Potpis

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

Re: Kontekstno slobodni jezici - zadatak 25.12.2009. u 08:47 · pre 205 meseci #4

Neka je $q(n)=n+p(n)$ , $k$ dužina pumpanja i $q(m)\geq k$ . Tada postoje reči $u,v,w,x,y$ takve da je $a^mb^{p(m)}=uvwxy$ , $|vx|>0$ , $|vwx|\leq k$ i tako da za ma koje $i\in\mathbb N$ važi $uv^iwx^iy\in\mathbf L$ .

No, tada za svako $i\in N$ postoji $n_i\in N$ tako da je $q(n_i)=|uv^iwx^iy|=|uwy|+|vx|i$ , odakle je $q(n_{i+1})-q(n_i)=|vx|$ . Ukoliko je pak $p$ polinom stepena bar dva sa pozitivnim vodećim koeficijentom, postojaće $j_0\in N$ takvo da za sve $t\geq j_0$ važi $q'(t)>|vx|$ , a samim tim i $q(s)-q(t)>|vx|(s-t)\geq|vx|$ za $s\geq t+1$ . Tada će takođe za $n_i,n_{i+1}\geq j_0$ biti ispunjeno $n_{i+1}>n_i$ , pa za $t=n_i$ i $s=n_{i+1}$ imamo kontradikciju.

Potpis

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

Re: Kontekstno slobodni jezici - zadatak 25.12.2009. u 11:11 · pre 205 meseci #5

Citat:

Goran Rakić: Dovoljno je pokazati da tvrđenje ne važi za $p(n) = n^2$ 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 $p(n) = \sum_{i=0}^{k} a_i x^i$ , što mi nikako nije uspevalo.

Hvala puno.

Re: Kontekstno slobodni jezici - zadatak 25.12.2009. u 12:54 · pre 205 meseci #6

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

Potpis

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

Re: Kontekstno slobodni jezici - zadatak 25.12.2009. u 13:19 · pre 205 meseci #7

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 $p(n)=n^2$ može da se uopšti.

Re: Kontekstno slobodni jezici - zadatak 25.12.2009. u 19:46 · pre 205 meseci #8

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.

Potpis

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

Re: Kontekstno slobodni jezici - zadatak 25.12.2009. u 20:41 · pre 205 meseci #9

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 $p(n) = \sum_{i=0}^{k}{n^i}$ stepena k.

Dalje po binomnoj formuli $p(n+1) = \sum_{i=0}^{k}{n^i} + \sum_{i=2}^{k}{\left( \sum_{j=1}^{i-1}{ {i \choose j} n^{i-j}} \right)} + (n+1)$ .

Za $k>1$ uz $n>0$ dobija se druga nejdnakost potrebna za kontradikciju da je napumpana reč duža od $a^nb^{p(n)}$ , a kraća od $a^{(n+1)}b^{p(n+1)}$ .

Potpis

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

Re: Kontekstno slobodni jezici - zadatak 25.12.2009. u 22:23 · pre 205 meseci #10

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.

Potpis

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

Forum kao aplikacija na telefonu

Srodne teme