sappa, kuuluvad saadud xz ja yz mõlemad keelde L või ei kuulu mõlemad). Teoreem: Keel L on regulaarne parajasti siis, kui seose HL ekvivalentsiklasside hulk on lõplik. T: (tarvilikkus) Kui keel L on regulaarne, leidub teda aktsepteeriv lõplik automaat M = (Q , Σ, δ, q0, F). Olgu R0i ⊆ Σ* sõnede hulk, mis viib automaadi M lähteolekust q0 olekusse qi. Seose HL ekvivalentsiklass on lõplik ühend Cl = R0i1 ∪ R0i2 ∪ . . . ∪ R0il. (piisavus) Olgu HL ekvivalentsiklassid C0,…,Cm. Teeme lõpliku automaadi olekute hulgaga Q = {C0…Cm}: Valime algolekuks klassi C0, mis sisaldab ε-d. Olgu lõppolek Ck ekvivalentsiklass, mis ühtib keelega L ehk kui x ∈ Ck ja x ∈ L, siis kui y ∈ Ck y ∈ L. Kui x ∈ Ci ja y ∈ Ci, st xz ∈ L yz ∈ L, siis kuuluvad sõned xa ja ya ka ühte klassi Cj. Tõepoolest: kui z = az′, siis xaz′ ∈ L yaz′ ∈ L iga z′ ∈ Σ* korral. Lisame automaati
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 
