Потисен автомат

Од Википедија, слободната енциклопедија
Прејди на: содржини, барај
Шема на потисен автомат

Потисниот автомат е конечен автомат кој употребува склад за чување на податоците.

Операции[уреди]

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

  • Го користат врвот на магацинот за да одлучат која преминувачка функција да ја извршат.
  • Располагаат со магацинот за време на преминувачката функција.

Потисниот автомат одбира преминувачка функција со обележување табела со влезни сигнали, моментална состојба, и врвот на магацинот. Нормалните конечни автомати бараат само влезен сигнал и моментална состојба: тие немаат магацин за да го искористат. Потисните автомати го додаваат магацинот како параметар по избор. Со давање влезен сигнал, моменталната состојба, и дадениот симбол на врвот на магацинот, патеката за преминувачка функција е избрана.

Потисните автомати исто така го користат магацинот, како дел за извршување на преминувачката функција. Нормалните конечни автомати одбираат нова состојба, а како резултат се појавува преминувачката функција. Користењето на магацинот се наоѓа за поставување на одреден симбол на врвот на магацинот, или за да се види што има на врвот на магацинот. Автоматот може и да не го користи магацинот, и да го остави таков каков што е. Изборот за управување (или не управување) зависи од табелата на премини.

Составување: Со даден влезен сигнал, моментална состојба, симбол на магацинот, автоматот ќе премине во друга состојба и евентуално ќе раководи (потисне или истакне) со магацинот.

Горнонаведениот конечен автомат е исклучиво недетерминистички конечен автомат, или во техниката познато како „недетерминистички потисен автомат“ (NPDA). Ако детерминистички конечен автомат, е користен, тогаш резултатот е детерминистички конечен автомат, (DPDA), кој е многу послаба направа. Недетерминизмот означува дека во еден автомат може да има повеќе од еден премин кој води до финална состојба, со даден влезен сигнал, состојба, и симбол на магацинот. Ако на еден конечен автомат му дадеме два магацина на располагање, ќе добиеме многу помоќна направа, по моќ еднаква со моќта на Тјуринговата машина.

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

Дефиниција[уреди]

NPDA W може да биде дефиниран како 7-торка: W = (Q,Σ,Φ,σ,s,Ω,F) каде

   Q  е конечно множество од состојби 
        Σ е конечно множество од влезна азбука
        Φ е конечно множество од азбука на магацинот 
        σ (понекогаш δ) е конечна преминувачка функција
          Formula1.jpg
        s е елемент од Q почетната состојба 
        Ω е почетниот симбол на магацинот 
        F е подмножество од  Q, што содржи конечни состојби. 

Постојат два вида на критериуми за прифатлива состојба: прифаќање кога магацинот е празен и прифаќање според конечната состојба. И ќе се покаже дека тие се еквивалентни меѓусебно: финална состојба може да овозможи кружно празнење на магацинот, а мачината може да детектира празен магацин и да внесе финална состојба при наоѓање на единствен симбол кој е внесен при почетна состојба. Некои користат 6- торки, исклуќувајќи ја Ω конечно множество од азбука на магацинот, наместо да го додадат првиот премин кој го запишува почетниот симбол на магацинот.

Пример[уреди]

Контексно слободната граматика {ak bkI k ≥0} може да биде препознаена од следниов потисен автомат: Formula3.jpg

Каде преминувачки функции се

δ(q0 ,a, ε) = {( q1 , A)}

δ(q1,a,ε) = {(q1,A)}

δ(q1,b,A) = {(q2,ε)}

δ (q1 ,b, A) = {( q3 , ε )}

δ(q1,a,ε) = {(q1,A)}

δ(q2,b,A) = {(q2,ε)}

δ (q2 ,b, A) = {( q3 , ε )}

δ (q, θ ,ρ)= ø за секое друго (q, θ ,ρ)

Гледајќи во во првиот премин се добива идејта за преминувачките функции δ(q0 ,a, ε) = {( q1 , A)}

Кога q0 е моменталната состојба, a е влезот, ε е земено од врвот на магацинот тогаш состојбата се менува во q1 и A го пишуваме на врв на магацин.

Psh1.jpg

Детерминистички потисни автомати[уреди]

Во теорија на автомати, детерминистички потисен автомат e детерминистички конечен автомат што користи магацин кој содржи податоци. Поимот „потисен“ се однесува на притискање „надолу“,така што прототипот на овој автомат ќе содржи и бушена картичка за да ја прочита информацијата. ПОимот „детерминистички потисен автомат“ моментално се однесува на апстрактен автомат кој препознава детерминистички контексно-слободна граматика. Детерминистичкото потискање е послаба верзија на потсниот автоматот.

Дефиниција PDA M е дефиниран како 7-орка: M = (Q,Σ,Γ,q0,Z0,A,δ) кадешто

   Q е конечно множество од состојби
        Σ е конечно множество од влезна азбука
        Γ е конечно множество од азбука на магацинот
        q0 е почетна состојба, елемент од  Q 
        Z0 е почетниот симбол на магацинот, елемент од  Γ 
        A  е множество од конечни состојби, подмножество од Q 
        δ е конечна преминувачка функција  Slika1mie.jpg множество од 
 конечни подмножества на  Slika2mie.jpg

M е детерминистички ако ги исполнува следниве два услови:

За секое q ∈ Q,a ∈ Σ ∪ {Λ} , множеството δ(q,a,X) има највеќе еден елемент. За секое q ∈ Q,X ∈ Γ , ако Slika5.jpgØ , тогаш δ(q,a,X) = Ø за секое a ∈ Σ Постојат два вида на критериуми за прифатлива состојба: прифаќање кога магацинот е празен и прифаќање според конечната состојба. Овие два не се еквивалентни за детерминистички потисен автомат (иако тие се за недетерминистичкиот потисен автомат). Јазиците прифатени од испразнениот магацин се јазици прифатени од конечната состојба, исто така не постојат зборови во јазикот што е префикс на некој друг збор од јазикот.


Претворање на контексно-слободни граматики во потисни автомати[уреди]

Пример за претворање од горе надолу

Pushdown1.jpg

Pushdown2.jpg

Пример за претворање од долу нагоре

Pushdown3.jpg

Pushdown4.jpg