Deterministički potisni automat

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.

 Definicija 

DPA M se može definisati kao uređena sedmorka:

gdje

 je konačan skup stanja
 je konačan skup ulaznih znakova (ulazna abeceda)
 je konačan skup znakova steka (stekovna abeceda)
 je početno (ili inicijalno) stanje, element skupa  
 je početni znak steka, element skupa 
 je skup finalnih stanja, podskup skupa 
  je konačna relacija prijelaza partitivni skup (skup svih podskupova) skupa 

M je deterministički ako zadovoljava oba sljedeća uslova:
 Za svaki , skup  sadrži najviše jedan element.
 Za svaki , ako Ø, tada Ø 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.
Kategorija:Teorija automata