Pushdown автомат

Од Википедија, слободна енциклопедија

Содржина

1 Операции
2 Дефиниција
3 Пример
4 Детерминистички Pushdown Автомати
5 Конверзија на Контексно-Слободни Граматики во Pushdown автомати

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

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

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

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

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

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

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

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

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

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

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

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

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

Контексно слободната граматика {a^k b^kI k ≥0} може да биде препознаена од следниов pushdown автомат:

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

δ(q₀ ,a, ε) = {( q₁ , A)}

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

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

δ (q₁ ,b, A) = {( q₃ , ε )}

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

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

δ (q₂ ,b, A) = {( q₃ , ε )}

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

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

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

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

Во теорија на автомати, детерминистички pushdown автомат e детерминистички конечен автомат што користи магацин кој содржи податоци. Поимот "pushdown" се однесува на "притискање надолу",така што прототипот на овој автомат ќе содржи и punchcard за да ја прочита информацијата. Терминот "детерминистички pushdown автомат" (DPDA) моментално се однесува на апстрактен автомат кој препознава детерминистички контексно-слободна граматика. Детерминистичкиот pushdown е послаба верзија од pushdown автоматот.

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

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

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

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