Induktsioonireegli kohaselt on siis regulaarse avaldisega esitatav ka hulk Rij = Rn+1 ij, samuti ka L(M) = U {Rij | qi on algolek, qj on lõppolek}. 5 Keele regulaarsuse tarvilik tingimus (pumpamise lemma). Kui L on regulaarne keel, siis leidub konstant p, nii et iga sõne z ∈ L, |z| > p (sõnes on rohkem kui p tähte) on jaotatav kolmeks alamsõneks z = uvw, nii et |v| > 0 (keskmine osa pole tühi) ja uvjw ∈ L iga j = 0,1,2,... korral. T: Olgu L = L (M ), kus M = (Q , Σ, δ , Q0 , F ) ja Q = {q0 ,1 , . . . , qn }. Valime p = n. Siis sõne z = a1a2...an+1 aktsepteerimiseks peab automaat M tegema n+1 sammu. Järelikult vähemalt 1 olek peab korduma. Järelikult uw ∈ L(M), uvw ∈ L(M), uv2w ∈ L(M) jne. Keel L = {0n1n|n > 0} pole regulaarne. Sellise keele jaoks on vaja mälu. 6 Myhill-Nerode teoreem.
Siis deterministliku automaadi korral: (aw,P) (w,Q) Järeldused: Väited on ekvivalentsed: · L on paremlineaarne keel · L on regulaarne hulk · L on aktsepteeritav deterministliku lõpliku automaadi abil 12. Keele regulaarsuse tarvilikud tingimused. Pumpamise lemma (tarvilik tingimus): Olgu n olekuga deterministlik lõplik automaat M. Iga sõna z, mida automaat aktsepteerib ning mille korral |z|>n, on esitatav kujul z = uvw sellisel viisil, et iga j>=0 jaoks ka uvjw kuulub automaadiga aktsepteeritavate (ehk keele sõnade hulka). Tõestus: Automaadi poolt skaneerimisel tehakse taktid delta(a,p) = q Sõna z = a1a2a3a4 korral on skaneerimine taktide jada (a1a2a3a4,q0)(a1a2a3,q1)* (e,qf). Kui z>n, peab mõni olek (näiteks olek r esinema korduvalt, masinas olema tsükkel vastasel juhul peaks masina olekute arv olema lõpmatu). Masina tsüklilises osas tekibki sõna keskele 0..lõpmatu arv stringe v.
annaabi.ee 
