Matfyz Wiki
Kvíz klasika, na zákeřnosti co si vzpomínám
Máme slova u1..un, v1...vn, S je podmnožina {1..n}, a i1...in je nějaká permutace prvků z S, problém u_i1...u_in=v_i1..v_n je
a) algoritmicky nerozhodnutelný
b) algoritmicky rozhodnutelný
c) existuje Turingův stroj, který ten problém řeší
d) existuje Turingův stroj, který rozhoduje ten problém
správně b,c,d - jelikož v PKP se můžou prvky opakovat, tady máme konečný počet možností
Které regulární jazyky nad abecedou X nejdou více rozložit
a) prázdná množina
b) {\labda}
c) X
d) {x| x z X}
správně a,b ( d je to same jako b)
Víc si nevzpomínám na záludnosti a ústní : Sestrojit zásobníkový automat rozpoznávající prázdným zásobníkem {wcw^r | w z {a,b}*}, nejjednodušeji jednostavově, to mě napadlo později. Udělal jsem dvoustavový, ten bylo třeba převéct na bezkontextovou gramatiku a tu redukovat. Dále dokázat algoritmus redukce.
Hodně štěstí !