Deterministički potisni automat

U teoriji automata, deterministički potisni automat je konačni deterministički automat koji u svom radu koristi stek.

Izraz potisni se odnosi na operaciju unošenja podataka u stek, (engl. push, potisnuti), koja dodaje podatak na vrh steka. Termin „deterministički potisni automat“ se u teoriji računarstva odnosi na apstraktni matematički automat koji prepoznaje determinističke kontekstno-nezavisne jezike. Deterministički potisni automat je određena verzija potisnog automata. Interesantno je da deterministički potisni automati spadaju u pravu podgrupu potisnih automata za razliku od deterministički konačnih automata i nedeterministički konačnih automata.

Definicija uredi

Potisni automat 'M' se može definisati kao uređena sedmorka:

  gde važi:

  •   je konačan skup ulaznih znakova(ulazna azbuka)
  •   je azbuka stanja
  •   je azbuka potisnog spiska
  •   je početno stanje
  •   je početni simbol potisnog spiska
  •  , skup završnih konfiguracija
  •   je skup pravila prelaza.

Petorka   se naziva pravilo, a ako je   onda  -pravilo.

Konfiguracija potisnog automata M je trojka   gde je   reč koju će automat pročitati, a   unutrašnja konfiguracija automata (prvi karakter niske   je na vrhu potisnog spiska).

M je deterministički ako zadovoljava oba sledeća uslova:

  • Za svako  , skup   sadrži bar jedan element.
  • Za svako  , ako je  , tada je   za svako  

Postoje dva moguća kriterijuma za prihvatanje znakova: prihvatanje praznim potisnim spiskom i prihvatanje završnim stanjem. Ova dva kriterijuma nisu jednaka za determinističke potisne automate iako jesu za nedeterminističke potisne automate.