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