· Olek qk kuulub sõna analüüsil läbitavale teeele
w = w1w2...wm (m>=2) nii, et
o w1 on tee q1 .. qk läbi olekute {q1, .., qk-1}
o wm on tee qk .. qj läbi olekute {q1, .., qk-1}
o wn (1
Q0, F), mis aktsepteerib keelt A, on teisendatav sama keelt aktsepteerivaks deterministlikuks lõplikuks automaadiks M = (Q’, Σ, δ′, Q0′, F′). Kui mittedeterministlikul on k olekut, siis talle vastaval deterministlikul võib olla kuni 2k olekut. T: eeldame, et N-is pole ε-üleminekuid. 4 Regulaarsete avaldiste ja lõplike automaatide samaväärsus. Teoreem: Regulaarse avaldisega defineeritud keel on aktsepteeritav (mittedeterministliku) lõpliku automaadiga. T: vastavalt avadlise struktuurile saame rekursiivselt teha automaadi: Teoreem: Lõpliku automaadi poolt aktsepteeritav keel on defineeritav regulaarse avaldisega. T: Olgu M = (Q,Σ,δ,Q1,F) lõplik automaat olekute hulgaga Q = {q0,q1,…,qn}. Defineerime Rk ij kui sõnede hulga, mis viivad automaadi olekust qi olekusse qj vahepeal olekuid qk,...,qn läbimata. Hulk R0 ij = {a∈Σ | qj ∈ δ(qi ,a)} on lõplik ja seega esitatav regulaarse avaldisega.
annaabi.ee 
