Teoreetilibe informaatika kordamisküsimused
= {a,b}
= {aa,bb,abb}
= {aab,ba,b}
Ning indeksid <2;1;3> aabbabb = aabbab
Osade korral aga eksisteerib.
Koostame karakteristliku Turingi masina.
Näeme, et kuna seda genereeriva Turingi masina määramispiirkond pole
lahenduv hulk (mõnel korral jääb masin lõpmatusse tsüklisse).
Taandasime Posti vastavuse probleemi Turingi masina peatumisprobleemile.
Kontekstivabade keelte ühesuse mittelahenduvus:
Mitmete formaalsete keelte ühesuse mittelahenduvus tugineb posti vastavuse
mittelahenduvusele.
KV keel L.
Olgu antud sõnade paarid:
C = {(x1,y1),..,(xn,yn)} (vähemalt ühetähelised keele sõnad)
Ning naturaalarvud:
I = {1,2,..,n} (numbrid ei kuulu keelse sõnade hulka)
Defineerime hulgad:
Lc = {xi1 .. xim, im .. i1 | ik kuulub I, m>=1}
Mc = {ui1...yim im... i1 | ik kuulub I, m>=1}
Loome sellised magasinmäluga automaadid, mis aktsepteerivad keeled Lc ja Mc.
annaabi.ee 
