index předchozí 1 2 3 4 5 6 7 8 9 10 11 12 následující

Cvičení dvanácté

Postův korespondenční problém, nerozhodnutelné problémy z TAFJ, diagonalizace

1) Jsou dány seznamy A = x₁,x₂,...,x_n a B = y₁,y₂,...,y_n neprázdných slov nad danou abecedou. Je rozhodnutelné zda tato instance PKP ma řešení v případě, že ?:

n=1
n=2 (DÚ)
abeceda je jednopísmenková
|x_i|=|y_i| pro všechny i=1,2,...,n

2) A,B jsou seznamy z předcházejícího příkladu. Je rozhodnutelné určit, zda existují dvě posloupnosti čísel i₁,...,i_k a j₁,...,j_k
(i_r,j_r náleží {1,..,n} pro r = 1,..,k) takové, že x_i1,x_i2,...,x_ik = y_j1,y_j2,...,y_jk (DÚ)

3) Jsou násleující problémy rozhodnutelné?

R je regulární jazyk. Lze rozhodnout, zda co-R={} ?
R je regulární jazyk a L je bezkontextový jazyk. Lze rozhodnout, zda L průnik R={} ?
R₁,R₂ jsou regulární jazyky. Lze rozhodnout, zda R₁ je podmnožinou R₂ ?

4) Dokažte (s využitím diagonalizace), že existuje jazyk L, který není kontextový a je rekurzivní.