Plácám z hladu :o))

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
Urza

Plácám z hladu :o))

Příspěvek od Urza »

Zdarec :o))


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 :D

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 ? :shock:

Ta chyba bude nějaká dementně triviální , ale prostě už mi to nějak nemyslí a fakt ji tam nevidím .


Urza :twisted:
Urza

Re: Plácám z hladu :o))

Příspěvek od Urza »

U tý gramatiky jsem samozřejmě zapomněl na nějaký množinový závorky a tak , ale je to jasný , ne ? :lol:
Urza

Re: Plácám z hladu :o))

Příspěvek od Urza »

Najedl jsem se a taky jsem si odpověděl :D :D :D :D
Tak se omlouvám , že jsem rušil 8)
MIKI
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))

Příspěvek od MIKI »

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ť.
hardwire2
Matfyz(ák|ačka) level I
Příspěvky: 24
Registrován: 5. 1. 2008 19:57
Typ studia: Informatika Bc.

Re: Plácám z hladu :o))

Příspěvek od hardwire2 »

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 :)
MIKI
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))

Příspěvek od MIKI »

Tak nejak som si to vysvetloval aj ja. Len ma nejak miatla fraza "lubovolne slovo zeL"...
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ť.
peterblack
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 10. 12. 2006 19:26

Re: Plácám z hladu :o))

Příspěvek od peterblack »

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 :-D jestli tam jsou chyby tak je opravte
lickra
Matfyz(ák|ačka) level I
Příspěvky: 21
Registrován: 13. 6. 2006 22:24

Re: Plácám z hladu :o))

Příspěvek od lickra »

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.
peterblack
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 10. 12. 2006 19:26

Re: Plácám z hladu :o))

Příspěvek od peterblack »

pravda opravil jsem to aby to bylo srozumitelnější
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“