Potisni automat: razlika između inačica

Dodano 14 bajtova ,  prije 7 godina
bez sažetka
m (Bot: brisanje 23 međuwiki poveznica premještenih u stranicu d:q751443 na Wikidati)
No edit summary
U [[teorija automata|teoriji automata]], '''potisni automat''' je [[konačni automat]] koji koristiprimjenjuje podatkovnu strukturu ''stog''.
Termin "potisni" se odnosi na akciju "potiskivanja" ([[engleski jezik|engl.]] ''pushing down'') kojom bi prototipni mehanički automat fizički doticao bušenu karticu u svrhu iščitavanja njenog sadržaja. Termin "potisni automat" (PA) u teoretskom računarstvu se odnosi na apstraktni matematički stroj koji prepoznaje [[kontekstno neovisni jezik|kontekstno neovisne jezike]].
 
== Djelovanje ==
Potisni se automati razlikuju od normalnog konačnog automata na sljedeća dva načina:
# Mogu koristitiupotrebljavati vrh stoga kako bi odlučili koji prijelaz obaviti
# Mogu manipulirati sadržajem stoga prilikom obavljanja prijelaza
 
Potisni automati odabiru prijelaz indeksiranjem [[tablica prijelaza|tablice prijelaza]] sa ulaznim znakom (simbolom), trenutnim stanjem te vrhom stoga. Normalni konačni automati koristeupotrebljavaju samo ulazni znak i trenutno stanje: nemaju stoga nad kojim mogu obavljati promjene. Potisni automati dodaju stog kao parametar izbora. Za dani ulazni znak, trenutno stanje te dani znak na vrhu stoga, odabire se odgovarajući prijelaz.
 
Potisni automati također mogu manipulirati stogom prilikom obavljanja prijelaza. Normalni konačni automati kao rezultat obavljanja prijelaza odabiru novo stanje. Prilikom manipuliranja stogom može se na vrh stoga dodati (engl. ''push'') određeni znak, ili uzeti (engl. ''pop'') znak za vrha stoga. Automat može alternativno potpuno ignorirati sadržaj stoga, ne obavljajući nikakve operacije nad njim. Izbor manipuliranja (ili nemanipuliranja) sadržajem stoga je određeno funkcijom prijelaza.
Ukratko: Za dani ulazni znak, trenutno stanje te znak na vrhu stoga, potisni automat može preći u drugo stanje, te opcionalno manipulirati (dodati znak ili uzeti znakove) sadržajem stoga.
 
Ako je (pozadinski) konačni automat konkretno [[nedeterministički konačni automat]], dobivamo stroj koji je tehnički poznat pod nazivom "nedeterministički potisni automat" (NPA). UkolikoAko se koristiupotrebljava [[deterministički konačni automat]], kao rezultat dobivamo [[deterministički potisni automat]] (DPA), strogo slabiji uređaj.
Nedeterminizam u ovom kontekstu ne označava pojavu slučajnih događaja, već označava mogućnost više od jednog prijelaza za dani ulazni znak, stanje i znak na vrhu stoga.
 
Dva su moguća kriterija prihvaćanja niza znakova: prihvaćanje ''praznim stogom'' i prihvaćanje ''prihvatljivim stanjem''. Lako se može pokazati da su oba kriterija istovjetna: konačno stanje može u petlji uzimati znakove sa vrha stoga sve dok se sadržaj stoga ne isprazni, a i stroj može detektirati prazni stog i preći u prihvatljivo stanje detektiranjem jedinstvenog znaka kojeg na vrh stoga dodaje početno stanje.
 
Ponegdje se u formalnoj definiciji potisnog automata koristirabi i uređena šestorka, izuzimajući <math>\Omega</math> kao početni znak stoga, i umjesto istaknutog znaka stogovne abecede dodaju prvi prijelaz koji dodaje početni znak na vrh stoga.
 
== Primjer ==