Teoreetilibe informaatika kordamisküsimused
L või ei kuulu sellesse.
HL on ekvivalentsiseos, kuna xzHxz, xzHyz <=> yzHxz, xzHwz AND wzHyz =>
xzHyz.
Myhill ja Nerode väitsid, et keel on regulaarne parajasti siis, kui seose H
ekvivalentsiklasside hulk on lõplik.
Tarvilikkuse tõestus:
Moodustame keelt L aktsepteeriva lõpliku automaadi M = (,Q,delta,Q0,F).
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 .
annaabi.ee 
