Ekvivalenca nedeterminističnih končnih avtomatov s praznimi prehodi in nedeterminističnih končnih avtomatov brez praznih prehodov

Iz MaFiRaWiki

Zmožnost praznih prehodov nedeterminističnim končnim avtomatom ne omogoča, da bi razpoznavali neregularne množice.

Ker so nedeterministični končni avtomati s praznimi prehodi posplošitev NKA, zagotovo razpoznavajo regularne izraze (ekvivalenca determinističnih in nedeterminističnih končnih avtomatov). Sedaj pokažimo, da razpoznavajo natanko regularne jezike. Oznake in funkcije, ki jih bomo uporabili v dokazu, so definirane v članku Nedeterministični končni avtomati s praznimi prehodi.

Naj bo L jezik, ki ga razpoznava NKA-ε M=(Q,Σ,δ,q0,F). Konstruiramo M'=(Q,Σ,δ',q0,F'), da velja:

  • F'={ F ∪ {q0}, če ε-ZAPRTJE(q0) vsebuje stanje F, sicer F}
  • δ'(q,a)=δ*(q,a) za q∈ Q in a∈ Σ

Sedaj bomo pokazali z indukcijo glede na dolžino niza x, da je

δ'(q0,x)=δ*(q0,x).

Ta izjava ni nujno resnična, če je x=ε, saj δ'(q0,ε)={q0}, medtem ko δ*(q0,ε)= ε-ZAPRTJE(q0), zato bomo začeli indukcijo pri 1.

Baza indukcije: Če je dolžina niza x 1, je x nek simbol a abecede Σ in velja δ'(q0,a)=δ*(q0,a) po definiciji δ'.

Indukcijska predpostavka: Naj bo dolžina niza strogo več kot 1. x=wa, a∈ Σ. Za vse nize v dolžine manj od x velja δ'(q0,v)=δ*(q0,v).

Indukcijski korak: δ'(q0,wa)=δ'(δ'(q0,w),a). Po indukcijski predpostavki velja δ'(q0,w)=δ*(q0,w). Naj bo δ*(q0,w)=P. Pokazati moramo, da je δ'(P,a)=δ*(q0,wa). Ampak δ'(P,a)= \bigcup_{q\in\mathbf{P}}δ'(q,a)=\bigcup_{q\in\mathbf{P}}δ*(q,a). Ker je P=δ*(q0,w), dobimo \bigcup_{q\in\mathbf{P}}δ*(q,a)=δ*(q0,wa) po definiciji δ*. Torej δ'(q0,wa)=δ*(q0,wa). S tem smo dokazali predpostavko za poljubno dolžino niza x.

Da pokažemo ekvivalenco končnih avtomatov, še moramo premisliti, da δ'(q0,x) vsebuje stanje iz F' natanko tedaj ko δ*(q0,x) vsebuje stanje F.

Če je x prazen niz, to sledi neposredno iz definicije F'. δ'(q0,ε)={q0}, q0 pa je v F' kadar δ*(q0,ε)(ε-ZAPRTJE(q0)) vsebuje stanje v F. Če x ni prazen niz, ga zapišemo kot x=wa za nek simbol a. Če δ*(q0,x) vsebuje stanje F, potem δ'(q0,x) vsebuje isto stanje v F'.

Obratno: če δ'(q0,x) vsebuje stanje iz F' različno od q0, potem δ*(q0,x) vsebuje stanje iz F. Če δ'(q0,x) vsebuje q0 in q0 ni v F, potem zaradi δ*(q0,x) = ε-ZAPRTJE(δ(δ*(q0,w),a)) stanje v ε-ZAPRTJE(q0) in v F mora biti v δ*(q0,x).

Osebna orodja