Deterministički potisni automat
Sa Wikipedije, slobodne enciklopedije
U teoriji automata, deterministički potisni automat je deterministički konačni automat koji koristi podatkovnu strukturu stek. Termin "potisni" se odnosi na akciju "potiskivanja" (engl. pushing down) kojom bi prototipni mehanički automat fizički doticao bušenu karticu u svrhu iščitavanja njenog sadržaja. Termin "deterministički potisni automat" (DPA) u teoretskom računarstvu se odnosi na apstraktni matematički automat koji prepoznaje determinističke kontekstno nezavisne jezike.
Deterministički potisni automat je slabija verzija potisnog automata.
[uredi] Definicija
DPA M se može definisati kao uređena sedmorka:
M = (Q,Σ,Γ,q0,Z0,A,δ) gdje
- Q je konačan skup stanja
- Σ je konačan skup ulaznih znakova (ulazna abeceda)
- Γ je konačan skup znakova steka (stekovna abeceda)
- q0 je početno (ili inicijalno) stanje, element skupa Q
- Z0 je početni znak steka, element skupa Γ
- A je skup finalnih stanja, podskup skupa Q
- δ je konačna relacija prijelaza
partitivni skup (skup svih podskupova) skupa 
M je deterministički ako zadovoljava oba sljedeća uslova:
- Za svaki
, skup δ(q,a,X) sadrži najviše jedan element. - Za svaki
, ako 
Ø, tada δ(q,a,X) = Ø za svaki 
Dva su moguća kriterija prihvatanja niza znakova: prihvatanje praznim stekom i prihvatanje prihvatljivim stanjem. Lahko se može pokazati da su oba kriterija istovjetna: konačno stanje može u petlji uzimati znakove sa vrha steka sve dok se sadržaj steka ne isprazni, a i automat može detektovati prazan stek i preći u prihvatljivo stanje detektiranjem jedinstvenog znaka kojeg na vrh steka dodaje početno stanje.
