# Zkouška - 3.6.2013

<{ForumPost(poster="MadMan", timestamp=2013-06-03 13:13:36)}>
Kvíz klasika, na zákeřnosti co si vzpomínám  
  
1) 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í  
  
2) 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í !
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2013-06-03 13:42:11)}>
oprava: u 2) d je to same jako c
<{/ForumPost}>