Недетерминистички коначни аутомат

У теорији израчунавања, недетерминистички коначни аутомат (НДКА) је коначни аутомат у коме за сваки пар стања и улазног карактера може да постоји више стања у која се може прећи. Ово их разликује од детерминистичких коначних аутомата (ДКА), код којих је следеће стање једнозначно одређено. Иако НДКА и ДКА имају различите дефиниције, може се показати у формалној теорији да су они еквивалентни. За сваки НДКА може се конструисати еквивалентан ДКА, и обратно. Оба типа аутомата препознају само регуларне језике. НДКА су генерализовани помоћу пробабилистичких аутомата, са пробабилистиком у смислу избора следећег стања, када постоји избор.

НДКА су уведени од стране Мајкла О. Рабина и Дана Скота 1959, који су указали на њихову еквивалентност са ДКА.

Интуитиван прилаз

НДКА, исто као и ДКА, обрађује ниску улазних карактера. За сваки симбол са улаза прелази у једно од могућих стања на основу тренутног стања и прочитаног симбола. У том смислу је уобичајено говорити о скупу могућих стања, као члану партитивног скупа скупа стања. Сада прелаз није само стање, већ неки подскуп стања.

Проширење НДКА је НДКА-ламбда (НДКА-ε, НДКА са епсилон прелазом), који допушта прелаз из неког стања у неко друго без читања знака са улаза. Овакав прелаз се назива епсилон прелаз. Уобичајено је да се обележава са λ или ε.

Ознака за прихватање знака са улаза је иста као и код ДКА. Кад и последњи знак буде прочитан, ниска ће бити прихваћена ако и само ако постоји низ прелаза којима аутомат са овим улазом може завршити у прихватајућем стању. Односно, неће бити прихваћена ако за сваку комбинацију прелаза аутомат завршава у неприхватајућем стању.

Формална дефиниција

НДКА је уређена 5-торка (Q, Σ, T, q₀, F), која се састоји од:

• коначног скупа Стања Q
• коначног скупа улазних симбола Σ
• функције прелаза T : Q × Σ → P(Q).
• почетног стања q₀, q₀ $\in$ Q
• скупа завршних стања F, F $\in$ Q.

P(Q) означава партитиван скуп скупа Q. НДКА са ε покретима замењује функцију прелаза функцијом која дозвољава празну реч ε као могућ улаз, према томе имамо функцију T : Q × (Σ $\cup$ {ε}) → P(Q).

Може се показати да су НДКА и НДКА-ε еквивалентни и да се може један конструисати на основи другог и обратно. Што значи да препознају исти језик.

Карактеристике

Аутомат почиње са радом у изабраном почетном стању и чита ниску симбола сачињену од његове улазне азбуке. Да би одредио наредно стање у које треба прећи, користи функцију прелаза Т. На основу учитаног знака и стања у коме се нашао читајући тај знак, на располагању му је неко од стања из скупа могућих наредних стања.

Скуп свих ниски које прихвата аутомат НДКА се назива језиком тог аутомата. Тај језик је регуларан.

За сваки НДКА може се конструисати одговарајући ДКА који препознаје исти језик. Ово је са циљем поједностављења аутомата и може се постићи конструкцијом скупа подскупова.

За недетерминистичке коначне аутомате са пребројиво много стања конструкција подскупова даје аутомат са скупом стања моћи континуума. У том случају над скупом стања се мора успоставити нека топологија. Овакви системи се проучавају као тополошки аутомати.

Карактеристике НДКА-ε

За све p, q $\in$ Q, пише се p →_ε q ако и само ако се из стања p може прећи у стање q, а да се при томе не прочита ни један знак са улаза. Или другим речима p →_ε q ако и само ако постоје стања q₁, q₂, ..., q_k $\in$ Q таква да важи:

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

За свако p $\in$ Q скуп стања која се могу достићи из p на овај начин се назива епсилон затворење стања p, и записује се: E({p}) = {q $\in$ Q : p →_ε q}.

За сваки подскуп P скупа Q, дефинише се епсилон затворење скупа P: E(P) = $\cup$ E({p}).

Епсилон затворења су транзитивна, па стога важи да за све q₀, q₁, q₂ $\in$ Q и за подскуп P скупа Q, важи: ако q₁ $\in$ E({q₀}) и q₂ $\in$ E({q₁}) онда q₂ $\in$ E({q₀}).

Слично, ако q₁ $\in$ E({P}) и q₂ $\in$ E({q₁}) онда q₂ $\in$ E({P}).

Нека је x ниска знакова над азбуком Σ $\cup$ {ε}. НДКА М препознаје (прихвата) ниску x ако постоји низ облика x₁x₂ ... x_n, где x_i $\in$ (Σ $\cup$ {ε}), и постоји низ стања p₀,p₁, ..., p_n, где p_i $\in$ Q, такви да задоваљавају следеће услове:

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

Имплементација

Постоји више начина којим се може остварити НДКА:

• Конструисати еквивалентан ДКА. У неким случајевима ово може проузроковати експоненцијалан раст броја стања аутомата, самим тим и такав раст потребног меморијског простора.
• Може се чувати структура података која ће чувати сва стања у којима аутомат тренутно може бити. При посматрању последњег знака са улаза ако је неко од тих стања завршно, ниска ће бити прихваћена. У најгорем случају ово може захтевати помоћни простор величине пропорцијалне величини броја стања НДКА. Ако структура података користи један бит по стању НДКА, ово решење је слично претходном.
• Стварају се вишеструке копије. За сваку одлуку о гранању у n стања НДКА креира до n-1 копија аутомата. Свака копија улази у посебно стање. Ако се приликом читања последњег знака бар један аутомат налази у завршном стању, НДКА ће прихватити ниску. Ово такође захтева линеарни простор од броја стања НДКА, будући да за свако стање може постојати по једна копија аутомата.
• Експлицитно се пропагирају поједини знакови кроз прелазну структуру НДКА и забележи се кад год токен достигне завршно стање. Ово је понекад корисно када је потребно да НДКА енкодира додатни контекст о догађајима који су потегли прелаз. За програмско остварења ове технике која прати референце на објекат погледати Tracematches.

Пример

Следећи пример објашњава НДКА М са бинарном азбуком, који са улаза прихвата ниску ако се садржи од парног броја јединица или парног броја нула. Нека је M = (Q, Σ, T, s₀, F) где је:

• Σ = {0, 1},
• Q = {s₀, s₁, s₂, s₃, s₄},
• E({s₀}) = { s₀, s₁, s₃ }
• F = {s₁, s₃}, и
• функција прелаза T се може дефинисати преко дијаграма прелаза:

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

Дијаграм прелаза за M је:

M се може представити као унија два ДКА: први са стањима {S₂, S₁}, други са стањима {S₃, S₄}.

Језик аутомата M се може описати као регуларан језик дат овим регуларним изразом: (1*(01*01*)*) $\cup$ (0*(10*10*)*)

Литература

• Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 978-0-534-94728-6.. (видети поглавље 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.. (видети поглавље 2)