Teoreetilibe informaatika kordamisküsimused
Mc = {ui1...yim im... i1 | ik kuulub I, m>=1}
Loome sellised magasinmäluga automaadid, mis aktsepteerivad keeled Lc ja Mc.
Osutub, et hulgal C saab koostada Posti vastavuse parajasti siis, kui Lc ühend
Mc-ga ei ole tühihulk .. ehk siis kui leidub kummaski selline järjestus, mis vastab
Posti järjestuse definitsioonile.
KV-keelte ühesus:
Moodustame hulga C alusel grammatika G = ( U I, {S,A,B},P,S), kus
produktsioonide hulk evib kolme liiki prod:
S A, S B,
A xiAi
B yiAi
A xii (i on siis number), B yii
Keeled Lc ja Mc on ühesed. Keel L(G) pole ühene, kui sõnale x eksisteerib
vähemalt 2 vasaktuletust. Selline situatsioon on võimalik ainult siis, kui see sõna
kuulub nii Lc kui Mc parajasti siis, kui Posti vastavuse probleem pole lahenduv.
33. Algoritmide keerukuse hindamine. Ülesannete keerukusklassid.
Turingi masina ajaline keerukus T(M) n mitu takti kulub, kus |x| = n.
Turingi masina mahuline keerukus S(M) n mitu pesa kulub
annaabi.ee 
