PKP

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.

PKP

Příspěvek od Him »

http://ktiml.mff.cuni.cz/~bartak/automa ... ture12.pdf

nemohl by mi někdo pls napsat:

1] jak si mám vysvětlit ty tečky na str. 4, slajd na pozici 1x1?
2] a kde se vzala ta tabulka na slajdu 2x1?

Myšlenka toho důkazu je ta, že PKP převedu na turingův stroj, o kterém víme, že se nemusí zastavit na nějakých slovech => problém je nerozhodnutelný. Ale jak vznikla ta tabulka a jaký vztah má u a v k w - to už mi jasné není

Díky za pomoc
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 ;)
beny
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 31. 1. 2008 12:51
Typ studia: Informatika Bc.

Re: PKP

Příspěvek od beny »

Ahoj!
Ted jsem na to PKP koukal a myslim, ze tem teckam rozumim. On si schvalne slova ui a vi upravil tak, ze mezi pismena tech slov nacpal tecky, a to dvojim zpusobem:
a) Bud dava tecky mezi vsechna pismena slova a i na zacatek nebo
b) dava tecky mezi vsechna pismena slova a i na konec

Nyni xi a yi jsou preteckovana pro indexy od 2 do n+1 a x(i+1) je preteckovane ui, obdobne pro y a v. Pro index n+2 tam ma pomocna slova x(n+2) a y(n+2). Kdyz budu hledat PKP pro tyhle dvojice slov, tak musi zacinat dvojici (x1,y1), protoze vsechny ostatni dvojice se lisi v tecce na zacatku. Takze kdyz mam nalezeno PKP, odstranim z vybranych dvojic tecky a mam definovany seznam dvojic (ui,vi), ze resi PKP a navic prvni dvojici je (u1,v1), tedy mam PKP s inicialnim resenim.

Aspon myslim :).

Ten TS zatim nechapu.
Jonáš
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 19. 1. 2010 10:57
Typ studia: Informatika Mgr.

Re: PKP

Příspěvek od Jonáš »

Tady je pěkne vysvetleno PKP http://www.cs.vsb.cz/kot/animace.php
Je tam i dost dalších věcí.
Ten odkaz už tady na fóru je, ale pokud někdo hledá PKP, tak ho lépe najde tady.
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“