Formalne jazyky, primitivna rekurzia, PCP

Prosím Vás, viete mi poradiť aspoň s jednou úlohou či tvrdením? 1) Ktoré z nasledovných výrokov sú pravdivé? Pár slovami vysvetliť prečo....A) Problém zistiť, či dané slovo w patrí do jazyka definovaného pomocou konečného automatu možno zistiť v polynomiálnom čase vzhľadom na veľkosť vstupuB) Existuje funkcia, ktorá je rekurzívna, ale nie P.R.C) Problém zistiť, či každé riešenie PCP dĺžky <= k je algoritmicky riešiteľný.D) Každý nedeterministický polynomiálny problém možno redukovať na SAT.2)Dokážte, že funkcia PRNO(n), ktorá vypočíta n-TB´ prvočíslo je primitívne rekurzívna.3)Dokážte, že funkcia najmenší spoločný násobok N.S.N (a,b) je primitívne rekurzívna môžete použiť, že +,-,* sú prim.rek.4) Nájdite úplne primitívne rekurzívne odvovodnenie charakteristickej funkcie predikátu ∃x (y=x^2)