Ekvivalenca determinističnih in nedeterminističnih končnih avtomatov

Iz MaFiRaWiki

Ker so nedeterministični končni avtomati (nedeterministični končni avtomat) posplošitev determinističnih, je jasno, da med drugimi NKA razpoznavajo tudi regularne jezike (tj. jezike, ki jih razpoznavajo DKA). Izkaže se, da NKA razpoznavajo natanko regularne jezike oziroma da lahko za vsak NKA konstruiramo DKA, ki razpoznava isti jezik.

Naj bo M=\langle Q, \Sigma, \delta, q_0, F\rangle NKA, ki razpoznava jezik L. Sedaj definiramo DKA M'=\langle Q', \Sigma, \delta', q_0', F'\rangle na sledeč način:

  • Stanja M' so elementi potenčne množice M, tj. Q'=\mathcal{P}(Q). Element Q' bomo označili [q1, q2, ..., qi], pri čemer so q1, ..., qi ∈ Q. ([q1, q2, ..., qi] je eno samo stanje DKA!)
  • q0'=[q0]
  • F' je množica stanj v Q', ki vsebujejo končno stanje M
  • Sedaj definiramo prehodno funkcijo tako, da je δ'([q1, q2, ..., qi], a)=[p1, p2, ..., pj] natanko tedaj, ko δ({q1, q2, ..., qi}, a)={p1, p2, ..., pj} (Unija δ(qk,a) za k=1,...,i je množica stanj {p1, p1, ..., pj} - ta ima predstavnika [p1, p2, ..., pj] v Q')

Sedaj z indukcijo glede na dolžino niza x pokažimo, da velja

δ'(q0', x) = [q1, q2, ..., qi] natanko tedaj ko δ(q0, x) = {q1, q2, ..., qi}

Baza indukcije: Če je dolžina x 0, je x prazen niz (ε) in velja δ'(q0', ε)=[q0] natanko takrat, ko δ(q0, ε)={q0}, saj q0'=[q0] (po konstrukciji)

Indukcijska predpostavka: Recimo, da je naša hipoteza resnična za nize dolžine m ali manj.

Indukcijski korak: Naj bo xa niz dolžine m+1, pri čemer je a znak abecede. Potem velja δ'(q0', xa)= δ'( δ'(q0', x), a). Po indukcijski predpostavki je δ'(q0', x) = [p1, p2, ..., pj] natanko takrat, ko δ(q0, x) = {p1, p1, ..., pj}. Po definiciji δ' velja δ'([p1, p2, ..., pj], a)=[r1, r2, ..., rk] natanko takrat ko δ({p1, p2, ..., pj}, a)={r1, r2, ..., rk}. Torej δ'(q0', xa)=[r1, r2, ..., rk] natanko takrat ko δ(q0', xa)={r1, r2, ..., rk}, s čimer smo dokazali resničnost trditve tudi za nize dolžine m+1, torej za nize poljubne dolžine.

Dodajmo še, da je δ'(q0', x) v F' natanko takrat, ko δ(q0, x) vsebuje stanje končno stanje M (vsebuje element F)(to sledi neposredno iz trditve, ki smo jo dokazali). Torej L(M)=L(M'). S tem pa je dokaz končan.

Osebna orodja