Fórum studentů MFF UK

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

Ahoj!
Ted jsem na to PKP koukal a myslim, ze tem teckam rozumim. On si schvalne slova u_i a v_i 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 x_i a y_i jsou preteckovana pro indexy od 2 do n+1 a x_(i+1) je preteckovane u_i, 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 (x₁,y₁), 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 (u_i,v_i), ze resi PKP a navic prvni dvojici je (u₁,v₁), tedy mam PKP s inicialnim resenim.

Aspon myslim .

Ten TS zatim nechapu.

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.