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. DEF: Olgu keele L ⊆ Σ* (keel on kõigi sõnede hulga alamhulk) jaoks antud ekvivalentsiseos HL ⊆ Σ* × Σ* selline, et xHLy kehtib parajasti siis, kui iga z ∈ Σ* korral kehtib xz ∈ L yz ∈ L (iga suvalise z lisamisel x ja y 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.
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. Siit on näha, et kui keel ei võimalda sellist genereerimist, siis see kindlasti ei ole paremlineaarne, kui aga võimaldab, võib see olla paremlineaarne 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.
annaabi.ee 
