Teoreetilibe informaatika kordamisküsimused
Kuna pumpamise lemmaga saab näidata keele L = 0 n1n mitteregulaarsuse,
saame järeldada, et keelteklasside L3 on alamhulgaks L2-le sisalduvus on range.
Myhill-Nerode'I teoreem (piisav ja tarvilik tingimus keelte regulaarsuseks):
Olgu antu keel L stringide hulgast *.
Olgu antud seos HL on alamhulgaks * x *. H kehtib stringide x ja y vahel
parajasti siis, kui iga stringi z korral stringid xz ja yz kas kuuluvad korraga keelde
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
annaabi.ee 
