Plácám z hladu :o))
Plácám z hladu :o))
Zdarec ))
Celej den se učím AaG a už mi z toho hrabe .... teď koukám na jednu takovou věc a přijde mi , že jsem přišel na protipříklad , že neplatí Pumping Lema . Bude to nejspíš nějaká kravina a jak říkám , už melu z hladu a ani tam neumím najít chybu , prosím , pomozte
PL zní ( ze slidů ) takto :
Nechť L je regulární jazyk. Potom existuje přirozené číslo n takové, že libovolné slovo z e L, |z|>=n lze psát ve tvaru uvw, kde: |uv|<= n, 1<=|v| a pro všechna i>=0 uv(na i)w e L.
Jenomže přece L={aa} je reguálrní ( vytvoří ho např gramatika ( S , a , S , {S->aa} ) . Mno jo , ale kde je to v , jehož délka je větší , než 1 , který se dá pumpovat ?
Ta chyba bude nějaká dementně triviální , ale prostě už mi to nějak nemyslí a fakt ji tam nevidím .
Urza
Celej den se učím AaG a už mi z toho hrabe .... teď koukám na jednu takovou věc a přijde mi , že jsem přišel na protipříklad , že neplatí Pumping Lema . Bude to nejspíš nějaká kravina a jak říkám , už melu z hladu a ani tam neumím najít chybu , prosím , pomozte
PL zní ( ze slidů ) takto :
Nechť L je regulární jazyk. Potom existuje přirozené číslo n takové, že libovolné slovo z e L, |z|>=n lze psát ve tvaru uvw, kde: |uv|<= n, 1<=|v| a pro všechna i>=0 uv(na i)w e L.
Jenomže přece L={aa} je reguálrní ( vytvoří ho např gramatika ( S , a , S , {S->aa} ) . Mno jo , ale kde je to v , jehož délka je větší , než 1 , který se dá pumpovat ?
Ta chyba bude nějaká dementně triviální , ale prostě už mi to nějak nemyslí a fakt ji tam nevidím .
Urza
Re: Plácám z hladu :o))
U tý gramatiky jsem samozřejmě zapomněl na nějaký množinový závorky a tak , ale je to jasný , ne ?
Re: Plácám z hladu :o))
Najedl jsem se a taky jsem si odpověděl
Tak se omlouvám , že jsem rušil
Tak se omlouvám , že jsem rušil
-
- Matfyz(ák|ačka) level III
- Příspěvky: 186
- Registrován: 10. 12. 2004 22:35
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Re: Plácám z hladu :o))
Ta a ako to je? Ja som prezmenu nevyspany...
MOTTO-1: Nieje dôležité vedieť ale pochopiť!!!
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 24
- Registrován: 5. 1. 2008 19:57
- Typ studia: Informatika Bc.
- Login do SIS: mocno6am
Re: Plácám z hladu :o))
Ta věta říká, že existujě nějaký n, tak že blabla. Ale neříká, jaký to n je. V důkazu se za něj vzít počet stavů v nějakým automatu, kterej L rozpoznává, čili 3 v tomhle případě. Pak to tvrzení ale platí, protože pro každý slovo delší než 3 platí v tomhle případě cokoliv (protože žádný takový v L není).
BTW když je jazyk konečnej, tak si za n stačí vzít dýlku nejdelšího slova a pak to pro všechny slova delší než n (tj. žádný) platí taky
BTW když je jazyk konečnej, tak si za n stačí vzít dýlku nejdelšího slova a pak to pro všechny slova delší než n (tj. žádný) platí taky
-
- Matfyz(ák|ačka) level III
- Příspěvky: 186
- Registrován: 10. 12. 2004 22:35
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Re: Plácám z hladu :o))
Tak nejak som si to vysvetloval aj ja. Len ma nejak miatla fraza "lubovolne slovo zeL"...
Dik.
Dik.
MOTTO-1: Nieje dôležité vedieť ale pochopiť!!!
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.
-
- Matfyz(ák|ačka) level III
- Příspěvky: 153
- Registrován: 10. 12. 2006 19:26
Re: Plácám z hladu :o))
ono na wikipedii je formulace z ktery je to podle me videt lip (prepsal jsem pismenka aby odpovidali Bartakovi):
Pokud je jazyk L regulární, existuje číslo n > 0 tak, že každé slovo z z jazyka L, pro které platí |z| ≥ n, lze zapsat ve tvaru z = uvw, kde pro slova u, v a z platí, že |uv| ≤ n, |v| > 0 a uviw patří do L pro každé i≥0.
BTW pridal jsem tabulku chomskyho hierarchie a tohle formulaci do wiki: http://wiki.matfyz.cz/wiki/Automaty_a_g ... g.29_lemma
az to pristi rok budem opakovat jestli tam jsou chyby tak je opravte
Pokud je jazyk L regulární, existuje číslo n > 0 tak, že každé slovo z z jazyka L, pro které platí |z| ≥ n, lze zapsat ve tvaru z = uvw, kde pro slova u, v a z platí, že |uv| ≤ n, |v| > 0 a uviw patří do L pro každé i≥0.
BTW pridal jsem tabulku chomskyho hierarchie a tohle formulaci do wiki: http://wiki.matfyz.cz/wiki/Automaty_a_g ... g.29_lemma
az to pristi rok budem opakovat jestli tam jsou chyby tak je opravte
Re: Plácám z hladu :o))
Nemas tu tabulku uplne dobre. Lebo Chomskeho hierarchie ma jen 4 typy. Dalsi deleni nepatri do Chomskeho hierarchie. To su chytaky v kvizu. Mam to primo od doc. Bartaka.
-
- Matfyz(ák|ačka) level III
- Příspěvky: 153
- Registrován: 10. 12. 2006 19:26
Re: Plácám z hladu :o))
pravda opravil jsem to aby to bylo srozumitelnější