Nedeterministički konačni automat

U teoriji izračunavanja, nedeterministički konačni automat (NDKA) je konačni automat u kome za svaki par stanja i ulaznog karaktera može da postoji više stanja u koja se može preći. Ovo ih razlikuje od determinističkih konačnih automata (DKA), kod kojih je sledeće stanje jednoznačno određeno. Iako NDKA i DKA imaju različite definicije, može se pokazati u formalnoj teoriji da su oni ekvivalentni. Za svaki NDKA može se konstruisati ekvivalentan DKA, i obratno. Oba tipa automata prepoznaju samo regularne jezike. NDKA su generalizovani pomoću probabilističkih automata, sa probabilistikom u smislu izbora sledećeg stanja, kada postoji izbor.

NDKA su uvedeni od strane Majkla O. Rabina i Dana Skota 1959, koji su ukazali na njihovu ekvivalentnost sa DKA.

Intuitivan prilaz

NDKA, isto kao i DKA, obrađuje nisku ulaznih karaktera. Za svaki simbol sa ulaza prelazi u jedno od mogućih stanja na osnovu trenutnog stanja i pročitanog simbola. U tom smislu je uobičajeno govoriti o skupu mogućih stanja, kao članu partitivnog skupa skupa stanja. Sada prelaz nije samo stanje, već neki podskup stanja.

Proširenje NDKA je NDKA-lambda (NDKA-ε, NDKA sa epsilon prelazom), koji dopušta prelaz iz nekog stanja u neko drugo bez čitanja znaka sa ulaza. Ovakav prelaz se naziva epsilon prelaz. Uobičajeno je da se obeležava sa λ ili ε.

Oznaka za prihvatanje znaka sa ulaza je ista kao i kod DKA. Kad i poslednji znak bude pročitan, niska će biti prihvaćena ako i samo ako postoji niz prelaza kojima automat sa ovim ulazom može završiti u prihvatajućem stanju. Odnosno, neće biti prihvaćena ako za svaku kombinaciju prelaza automat završava u neprihvatajućem stanju.

Formalna definicija

NDKA je uređena 5-torka (Q, Σ, T, q₀, F), koja se sastoji od:

• konačnog skupa Stanja Q
• konačnog skupa ulaznih simbola Σ
• funkcije prelaza T : Q × Σ → P(Q).
• početnog stanja q₀, q₀ $\in$ Q
• skupa završnih stanja F, F $\in$ Q.

P(Q) označava partitivan skup skupa Q. NDKA sa ε pokretima zamenjuje funkciju prelaza funkcijom koja dozvoljava praznu reč ε kao moguć ulaz, prema tome imamo funkciju T : Q × (Σ $\cup$ {ε}) → P(Q).

Može se pokazati da su NDKA i NDKA-ε ekvivalentni i da se može jedan konstruisati na osnovi drugog i obratno. Što znači da prepoznaju isti jezik.

Karakteristike

Automat počinje sa radom u izabranom početnom stanju i čita nisku simbola sačinjenu od njegove ulazne azbuke. Da bi odredio naredno stanje u koje treba preći, koristi funkciju prelaza T. Na osnovu učitanog znaka i stanja u kome se našao čitajući taj znak, na raspolaganju mu je neko od stanja iz skupa mogućih narednih stanja.

Skup svih niski koje prihvata automat NDKA se naziva jezikom tog automata. Taj jezik je regularan.

Za svaki NDKA može se konstruisati odgovarajući DKA koji prepoznaje isti jezik. Ovo je sa ciljem pojednostavljenja automata i može se postići konstrukcijom skupa podskupova.

Za nedeterminističke konačne automate sa prebrojivo mnogo stanja konstrukcija podskupova daje automat sa skupom stanja moći kontinuuma. U tom slučaju nad skupom stanja se mora uspostaviti neka topologija. Ovakvi sistemi se proučavaju kao topološki automati.

Karakteristike NDKA-ε

Za sve p, q $\in$ Q, piše se p →_ε q ako i samo ako se iz stanja p može preći u stanje q, a da se pri tome ne pročita ni jedan znak sa ulaza. Ili drugim rečima p →_ε q ako i samo ako postoje stanja q₁, q₂, ..., q_k $\in$ Q takva da važi:

q₁ $\in$ T(p, ε), q₂ $\in$ T(q₁, ε), ..., q_k $\in$ T(q_k-1, ε).

Za svako p $\in$ Q skup stanja koja se mogu dostići iz p na ovaj način se naziva epsilon zatvorenje stanja p, i zapisuje se: E({p}) = {q $\in$ Q : p →_ε q}.

Za svaki podskup P skupa Q, definiše se epsilon zatvorenje skupa P: E(P) = $\cup$ E({p}).

Epsilon zatvorenja su tranzitivna, pa stoga važi da za sve q₀, q₁, q₂ $\in$ Q i za podskup P skupa Q, važi: ako q₁ $\in$ E({q₀}) i q₂ $\in$ E({q₁}) onda q₂ $\in$ E({q₀}).

Slično, ako q₁ $\in$ E({P}) i q₂ $\in$ E({q₁}) onda q₂ $\in$ E({P}).

Neka je x niska znakova nad azbukom Σ $\cup$ {ε}. NDKA M prepoznaje (prihvata) nisku x ako postoji niz oblika x₁x₂ ... x_n, gde x_i $\in$ (Σ $\cup$ {ε}), i postoji niz stanja p₀,p₁, ..., p_n, gde p_i $\in$ Q, takvi da zadovaljavaju sledeće uslove:

1. p₀ $\in$ E({q₀})
2. p_i $\in$ E(T(p_i-1, x_i )) za i = 1, ..., n
3. p_n $\in$ F.

Implementacija

Postoji više načina kojim se može ostvariti NDKA:

• Konstruisati ekvivalentan DKA. U nekim slučajevima ovo može prouzrokovati eksponencijalan rast broja stanja automata, samim tim i takav rast potrebnog memorijskog prostora.
• Može se čuvati struktura podataka koja će čuvati sva stanja u kojima automat trenutno može biti. Pri posmatranju poslednjeg znaka sa ulaza ako je neko od tih stanja završno, niska će biti prihvaćena. U najgorem slučaju ovo može zahtevati pomoćni prostor veličine proporcijalne veličini broja stanja NDKA. Ako struktura podataka koristi jedan bit po stanju NDKA, ovo rešenje je slično prethodnom.
• Stvaraju se višestruke kopije. Za svaku odluku o grananju u n stanja NDKA kreira do n-1 kopija automata. Svaka kopija ulazi u posebno stanje. Ako se prilikom čitanja poslednjeg znaka bar jedan automat nalazi u završnom stanju, NDKA će prihvatiti nisku. Ovo takođe zahteva linearni prostor od broja stanja NDKA, budući da za svako stanje može postojati po jedna kopija automata.
• Eksplicitno se propagiraju pojedini znakovi kroz prelaznu strukturu NDKA i zabeleži se kad god token dostigne završno stanje. Ovo je ponekad korisno kada je potrebno da NDKA enkodira dodatni kontekst o događajima koji su potegli prelaz. Za programsko ostvarenja ove tehnike koja prati reference na objekat pogledati Tracematches.

Primer

Sledeći primer objašnjava NDKA M sa binarnom azbukom, koji sa ulaza prihvata nisku ako se sadrži od parnog broja jedinica ili parnog broja nula. Neka je M = (Q, Σ, T, s₀, F) gde je:

• Σ = {0, 1},
• Q = {s₀, s₁, s₂, s₃, s₄},
• E({s₀}) = { s₀, s₁, s₃ }
• F = {s₁, s₃}, i
• funkcija prelaza T se može definisati preko dijagrama prelaza:

	0	1	ε
S0	{}	{}	{S1, S3}
S1	{S2}	{S1}	{}
S2	{S1}	{S2}	{}
S3	{S3}	{S4}	{}
S4	{S4}	{S3}	{}

Dijagram prelaza za M je:

M se može predstaviti kao unija dva DKA: prvi sa stanjima {S₂, S₁}, drugi sa stanjima {S₃, S₄}.

Jezik automata M se može opisati kao regularan jezik dat ovim regularnim izrazom: (1*(01*01*)*) $\cup$ (0*(10*10*)*)

Literatura

• Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 978-0-534-94728-6.. (videti poglavlje 1.2: Nondeterminism, pp. 47-63)
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts. 1979. ISBN 0-201-029880-X.. (videti poglavlje 2)