ZK 2009-06-23

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).
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

ZK 2009-06-23

Příspěvek od Him »

Od kamarada jsem ziskal otazky, ktere mel na "ustni" casti:

* napsat TS pro palindromy
* urcit do jaky skupiny podle Chomskeho jazyk patri a dokazat to


Zkousel jsem si to resit, kdybyste nasli chybu tak kricte:

1] Jenom slovne: Prectu prvni pismeno a ulozim si ho do stavu, na danou pozici dam specialni symbol s vyznamem "sem uz nechod". Pak bych jel s tim pismenem na konec a pokud by se schodovalo ulozene pismenko s poslednim, tak bych na tom poslednim znaku zase dal symbol "sem uz nechod". Takhle bych jezdil z jedne strany na druhou. Pokud bych dostal na konci prazdnou pasku, tak bych se prepnul do koncoveho stavu. Pokud bych narazil na spatne pismenko v prubehu prejizdeni z jedne strany na druhou, tak bych se prepnul do stavu, pro ktery neni definovana prechodova fce a tim skoncil.

Pozn. "sem uz nechod" ~ epsilon

2]

Myslenka:
1) Ukazu, ze jazyk neni regularni
2) udelam bezkontextovou gramatiku pro palindromy.

ad 1)Pro spor predpokladejme, ze jazyk je regularni. Dle Nerodovy vety existuje prava kongruence ~ konecneho indexu m na X* takova, ze L je sjednocenim jistych trid rozkladu X*/~.

Vezmu slova:

B
AB
AAB
...
A^(m+1)B

A a B jsou pismena abecedy

Dve slova padnou do stejne tridy ekvivalence (Dirichlet), oznacme je A^i.B a A^j.B (i /= j), plati pro ne tedy:

A^i.B ~ A^j.B

~ je prava kongruence, tedy ma platit:

A^i.B.A^(m-i) ~ A^j.B.A^(m-i) // pridam retezec A^(m-i) k oboum slovum

nicmene A^i.B.A^(m-i) \in L ale A^j.B.A^(m-i)
otIN L -- spor

Pozn. Pokud abeceda obsahuje pouze jedno pismeno, pak je L jiste regularni. Bezkontextovy je pro |X|>1
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
Kubees
Matfyz(ák|ačka) level II
Příspěvky: 65
Registrován: 12. 1. 2007 22:22
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: ZK 2009-06-23

Příspěvek od Kubees »

Ahoj,

huh, chvilku mi trvalo, nez jsem ten dukaz pobral, ale uz dobry, rozumim :-)

Jeste dodam ze podobnym zpusobem se totez da dokazat pres pumping lemma:
AAAABAAAA :arrow: patri do jazyka :arrow: napumpuju levou pulku :arrow: AAAAAAAABAAA :arrow: nepatri do jazyka :arrow: spor

Samozrejme je opet treba rict, ze toto plati pro slova delky > 2n kde n je vzdalenost pumpovane casti, ne pro tohle konkretni slovo, ale to je snad kazdemu jasne. :)
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“