Potisni automat: razlika između inačica
Izbrisani sadržaj Dodani sadržaj
m zamjena čarobnih ISBN poveznica predlošcima (mw:Requests for comment/Future of magic links) i/ili općeniti ispravci |
m RpA: WP:NI, WP:HRV |
||
Redak 7:
# Mogu manipulirati sadržajem stoga prilikom obavljanja prijelaza
Potisni automati odabiru prijelaz indeksiranjem [[tablica prijelaza|tablice prijelaza]]
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.
Redak 16:
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.
Ako dozvolimo konačnom automatu pristup dva stoga umjesto samo jednom, dobijemo znatno jači uređaj, istovjetan po moći
automata, ali i slabiji od Turingovog stroja.
Redak 36:
*<math>F</math> je podskup skupa <math>Q</math> koji čini skup prihvatljivih stanja
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
Ponegdje se u formalnoj definiciji potisnog automata rabi 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.
Redak 46:
<math>M = (\{q_0, q_1, q_2, q_3\}, \{a,b\}, \{A,\underline{A}\}, \delta, q_0, \{q_0, q_3\} ),</math>
<math>\delta(q_0, a, \epsilon) = \{(q_1, \underline{A})\} </math>
Redak 66:
<math>\delta(q_0, a, \epsilon) = \{(q_1, \underline{A})\} </math>
Kada je <math>q_0</math> trenutno stanje, <math>a</math> je ulazni znak i <math>\epsilon</math> je uzet
[[Datoteka:Automateapile.png]]
|