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

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

Операции

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

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

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

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

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

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

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

Дефиниција

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

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

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

Пример

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

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

δ(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 го пишуваме на врв на магацин.

Детерминистички потисни автомати

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

Дефиниција 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 ∈ Σ Постојат два вида на критериуми за прифатлива состојба: прифаќање кога магацинот е празен и прифаќање според конечната состојба. Овие два не се еквивалентни за детерминистички потисен автомат (иако тие се за недетерминистичкиот потисен автомат). Јазиците прифатени од испразнениот магацин се јазици прифатени од конечната состојба, исто така не постојат зборови во јазикот што е претставка на некој друг збор од јазикот.

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

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

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