Teoreetilibe informaatika kordamisküsimused
Moodustame hulgad:
R0i = {x | x on string, (x,qo) * (e,qi), q0 on algolek, qi on olek}
Seose H ekvivalentsiklass on esitatav ühendina:
Ck = R0i1 U ... U R0ik
Iga kahe sõna x kuulub R0i ja y kuulub R0i korral masin kas aktsepteerib neid
sõnu korraga või ei aktsepteeri tuleneb masina definitsioonist. Sõnu xz ja yz
aktseopteerib või ei aktsepteeri ta samuti korraga kuna alamsõna analüüs
algab samast olekust ning lõpeb samas.
R0i ei pruugi kokku langeda ekvivalentsiklassiga, kuna ka mõnest teisest olekust
qj lähtudes võib automaat samu sõnu aktsepteerida. Seega on
ekvivalentsiklassiks hulkade ühend.
Basically .. kuna automaadi olekute hulk on lõplik, on lõplik ka
ekvivalentsiklasside hulk.
Piisavuse tõestus:
Olgu H ekvivalentsiklassid C0, .., Cm. Koostame automaadi olekutega Q = {Ci} i
= 0,..,m. Algolekuks saab ekvivalentsiklass, mis sisaldab tühja sõna (C0 =
{e, ...}).
Kui aga ekvivalentsiklass sisaldab keele sõna, siis kuulub sellesse
annaabi.ee 
