Rekursiooni ja keerukusteooria eksami konspekt
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
annaabi.ee 
