Потисни аутомат

У теорији аутомата, потисни аутомат је коначни аутомат који користи стек за чување података.

Рад

дијаграм потисног аутомата

Потисни аутомати се од осталих коначних аутомата разликују у два аспекта:

Могу да користе врх стека да одреде који прелаз да искористе.
Могу да манипулишу стеком током спровођења прелаза.

Потисни аутомати бирају прелаз индексирањем табеле по улазном сигналу, тренутном стању, и врху стека. Обични кончани аутомати гледају само улазни сигнал и тренутно стање: они не поседују стек. Потисни аутомати додају стек као параметар при избору. За дати улазни сигнал, тренутно стање, и симбол на врху стека, одређује се прелаз који ће се извршити.

Потисни аутомати такође могу да манипулишу стеком у току спровођења прелаза. Обични коначни аутомати бирају ново стање које је резултат спроведеног прелаза. Поменута манипулација може да се састоји у гурању одређеног симбола на врх стека или у скидању симбола са врха стека. Такође, аутомат може да игнорише стек и да га остави у истом стању у коме је био. Избор манипулације (или њеног одсуства) је одређен таблицом прелаза.

Укратко: За дати улазни сигнал, тренутно стање и симбол на врху стека, аутомат може да прати прелаз у неко наредно стање и да опционално манипулише (изврши операцију уметања или скидања) над стеком.

Начелно, потисни аутомат може да спроведе неколико рачунских операција над датом улазном ниском, од којих неке могу да се заврше заустављањем и прихватањем ниске, док код других то није случај. Стога се јавља модел који је познат под називом недетерминистички потисни аутомат. Недетерминизам се састоји у том еда може да постоји више доступних прелаза за дати улазни сигнал, стање и симбол са врха стека. Ако у свакој ситуацији постоји тачно један доступан прелаз, онда се ради о детерминистичком потисном аутомату, што је строго слабији уређај.

Ако се коначни аутомат конструише тако да може да ради са не једним већ два стека, онда се добија моћнији уређај, који је по снази еквивалентан Тјуринговој машини. Линеарно ограничен аутомат је уређај који је моћнији од потисног аутомата, али мање моћан од Тјурингове машине.

Потисни аутомати су еквиваленни контекстно слободним граматикама: за сваку контекстно-слободну граматику постоји потисни аутомат, такав да је језик генерисан граматиком идентичан језику који аутомат препознаје, што је једноставно доказати. Теже је показати обратни случај: да за сваки потисни аутомат постоји контекстно слободна граматика таква да је језик који аутомат препознаје идентичан језику генерисаном том граматиком.

Формална дефиниција

Потисни аутомат се формално дефинише као уређена седморка:

$M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F)$ где је

$\,Q$ коначни скуп стања
$\,\Sigma$ је коначан скуп који се назива улазном азбуком
$\,\Gamma$ је коаначан скуп који се назива азбуком стека
$\,\delta$ је коначан подскуп од $Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma \times Q\times \Gamma ^{*}$ , релација прелаза.
$\,q_{0}\in \,Q$ је почетно стање
$\ Z$ је почетни симбол на стеку
$F\subseteq Q$ је скуп прихватајућих стања

Елемент $(p,a,A,q,\alpha )$ је прелаз аутомата $M$ . То значи да $M$ , у стању $p$ , са симболом $a$ на улазу и са симболом $A$ на врху стека, треба да прочита симбол $a$ , промени стање у $q$ , скине са врха стека $A$ , и замени га симболом $\alpha$ . Слово $\epsilon$ (епсилон) означава празну ниску а ' $(\Sigma \cup \{\varepsilon \})$ ' компонента релације прелаза се користи да формализује чињеницу да потисни аутомат може да било прочита слово са улаза или да настави, оставивши улаз недирнут.

Често се у литератури релација прелаза замењује (еквивалентном) формализацијом, где

$\,\delta$ је функција прелаза, која пресликава $Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma$ у коначан подскуп од $Q\times \Gamma ^{*}$ .

Овде $\delta (p,a,A)$ садржи све могуће акције у стању $p$ са $A$ на врху стека када се на улазу јави $a$ . Записује се $(q,\alpha )\in \delta (p,a,A)$ за функцију када $(p,a,A,q,\alpha )\in \delta$ важи за релацију. Треба имати у виду да је кључна реч у дефиницији коначан.

Рачунања

Корак потисног аутомата

Како би се формализовала семантика потисног аутомата, уводи се опис тренутне ситуације. Свака уређена тројка $(p,w,\beta )\in Q\times \Sigma ^{*}\times \Gamma ^{*}$ се назива тренутним описом $M$ , који укључује тренутно стање, део улазне траке који још није прочитан, и садржај стека (симбол који је на врху се налази на почетку). Релација прелаза $\delta$ дефинише корка-релацију $\vdash _{M}$ аутомата $M$ за тренутни опис. За инструкцију $(p,a,A,q,\alpha )\in \delta$ постоји корак $(p,ax,A\gamma )\vdash _{M}(q,x,\alpha \gamma )$ , за свако $x\in \Sigma ^{*}$ и за свако $\gamma \in \Gamma ^{*}$ .

Начелно, потисни аутомати су недетерминистички, што значи да за дати тренутни опис $(p,w,\beta )$ може да постоји више доступних корака. Сваки од ових корака може да буде изабран приликом израчунавања.

Код горње дефиниције, у сваком кораку се увек један симбол (врх стека) скида са стека, и замењује га онолико симбола колико је потребно. Последица тога је да нема корака који су дефинисани над празним стеком.

Рачунања потисног аутомата су низови корака. Израчунавање почиње у почетном стању $q_{0}$ са почетним стек симболом $Z$ на стеку, и ниском $w$ на улазној траци, па је иницијални опис $(q_{0},w,Z)$ . Постоје два начина прихватања. Потисни аутомат може било да прихвати ниску својим коначним стањем, што значи да се након што је прочитао улазну траку аутомат налази у прихватајућем стању (у $F$ ), или да прихвати празним стеком ( $\varepsilon$ ), што значи да је читање улаза испразнило стек. Први начин прихватања користи унутрашњу меморију (стање), док други користи спољашњу меморију (стек).

Формално се дефинише

$L(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(f,\varepsilon ,\gamma )$ за $f\in F$ и $\gamma \in \Gamma ^{*}\}$ (коначно стање)
$N(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(q,\varepsilon ,\varepsilon )$ за $q\in Q\}$ (празан стек)

Овде $\vdash _{M}^{*}$ представља рефлексивно и транзитивно затворење корака релације $\vdash _{M}$ што значи било који број узастопних корака (нула, један или више).

Теорема. За сваки потисни аутомат $M$ може да се конструише потисни аутомат $M'$ такав да је $L(M)=N(M')$ , и обратно, за сваки потисни аутомат $M$ може да се констрише потисни аутомат $M'$ такав да је $N(M)=L(M')$

Види још

Референце

Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-94728-6. Section 2.2: Pushdown Automata, pp. 101-114.

Спољашње везе

Недетерминистички потисни аутомат Архивирано на сајту Wayback Machine (31. октобар 2007) на сајту Planet Math on Planet Math.
JFLAP, симулатор неколико типова аутомата, укључујући недетерминистички потисни аутомат