Deterministički konačni automat

Iz Vikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu

U teoriji izračunavanja, deterministički konačni automat (DKA) je konačni automat u kome za svaki par stanja i ulaznog znaka postoji jedan i samo jedan prelaz u sledeće stanje. Deterministički konačni automati prepoznaju samo skup regularnih jezika.

DKA prima nisku znakova sa ulaza. Za svaki ulazni znak obavlja prelaz u stanje određeno funkcijom prelaza. Kada je pročitana cela niska, prihvatiće je ili odbaciti u zavisnosti od toga da li je u tom trenutku DKA u prihvatajućem ili neprihvatajućem stanju.


Formalna definicija[uredi]

DKA je uređena 5-torka (S, Σ, T, s, A), koja se sastoji od:

  • konačnog skupa stanja (S)
  • konačnog skupa znakova zvanog ulazna azbuka (Σ)
  • funkcije prelaza (T : S × Σ → S)
  • početnog (inicijalnog) stanja (s S)
  • skupa prihvatljivih stanja (A podskup od S)

Neka je M DKA takav da je = (S, Σ, T, s, A) i X = x0x1 ... xn niska znakova nad azbukom Σ. M prihvata niz znakova X ako postoje stanja r0, r1, ..., rn iz S takva da važi:

  1. r0 = s
  2. ri+1 = T(ri, xi), za i = 0, ..., n-1
  3. rn A.

Kao što je pokazano u prvom uslovu, početno stanje automata je s. U drugom uslovu se kaže da će za svaki znak ulaznog niza X automat preći u sledeće stanje koje je jednoznačno određeno funkcijom T. Treći uslov kaže da će automat prihvatiti niz X ako čitanjem poslednjeg znaka niza X automat prelazi u neko od završnih stanja. U suprotnom, kaže se da će automat odbiti ovu reč. Skup reči koje ovaj DKA prihvata formira jezik za koji kažemo da je jezik koji prepoznaje ovaj DKA.

DKA bez liste prihvatajućih (završnih) stanja i bez početnog stanja poznat je kao poluautomat.


Primer[uredi]

Sledeći primer je primer DKA M sa binarnom azbukom, koji prepoznaje niske nula i jedinica u kojima se 0 pojavljuje paran broj puta.

M = (S, Σ, T, s, A) gde je:

0
1
S1 S2 S1
S2 S1 S2

Ako je automat u stanju S1 to znači da je do sada pročitao sa ulaza paran broj nula, a ako je u stanju S2 znači da je pročitao neparan broj nula. Kad god se na ulazu pojavi 1 stanje automata ostaje nepromenjeno. Kada se pročita cela niska sa ulaza stanje u kome je u tom trenutku automat će nam pokazati da li je ta niska prihvaćena ili ne. Ako niska sadrži paran broj nula onda će automat M po završetku rada biti u prihvatajućem stanju S1. Dakle, ulaz će biti prihvaćen.

Jezik automata M je regularni jezik koji je opisan sledećim regularnim izrazom: (1*(0(1)*0)*)*

Prednosti i nedostaci[uredi]

DKA su jedan od najpraktičnijih modela izračunavanja, s obzirom na to da je za izračunavanje potrebno linearno vreme, konstantan memorijski prostor i postoji onlajn algoritam koji ih simulira. Za dva data DKA postoje efikasani algoritmi kojima se pronalazi DKA koji prepoznaje njihovu:

  • uniju,
  • presek,
  • rezliku.

Takođe postoje i efikasni algoritmi za pronalaženje:

  • da li DKA pepoznaje bilo koju nisku,
  • da li prepoznaje sve niske,
  • da li dva DKA prepoznaju isti jezik,
  • za konkretan jezik DKA sa minimalnim brojem stanja koji ga prepoznaje.

DKA su po moći izračunavanja ekvivalentni nedeterminističkim konačnim automatima.

Sa druge strane, konačni automati su ograničene moći u pogledu jezika koji mogu prepoznati. Mnogi jednostavni jezici, uključujući bilo koji problem koji zahteva veći memorijski prostor od konstantnog, ne mogu biti prepoznati pomoću DKA. Klasični primer jezika koga ne prepoznaje DKA je jezik zagrada, jezik koji se sastoji od pravilno uparenih otvorenih i zatvorenih zagrada, kao što je (()(())). Opštije, bilo koji jezik koji se sastoji od niski oblika anbn – konačan broj a-ova za kojim sledi isti taj broj b-ova, ne može biti prepoznat pomoću DKA. Ovde je reč o rekurziji čija dubina nije ograničena. Za svaki sledeći nivo rekurzije bi bilo potrebno novo stanje.


Takođe videti[uredi]

Literatura[uredi]

  • Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 0-534-94728-X. Poglavlje 1.1: Finite Automata, pp.31-47. Potpoglavlje "Decidable Problems Concerning Regular Languages" poglavlja 4.1: Decidable Languages, pp.152-155.4.4 DFA can accept only regular language
Teorija automata: formalni jezici i formalne gramatike
Hijerarhija
Čomskog
Gramatike Jezici Minimalni
automat
Tip-0 Bez ograničenja Rekurzivno prebrojivi Tjuringova mašina
% (bez uobičajenog imena) Rekurzivni Odlučivač
Tip-1 Kontekst senzitivna Kontekst senzitivni Linearno-ograničeni
% Indeksirana Indeksiran Ugnježdeni stek
Tip-2 Kontekst-slobodna Kontekst-slobodni Nedeterministički potisni
% Deterministička kontekst-slobodna Deterministički kontekst-slobodni Deterministički potisni
Tip-3 Regularna Regularan Konačni
Svaka kategorija jezika ili gramatika je pravi podskup kategorije direktno iznad nje.