Pushdown Automata

Pushdown Automata

კომპიუტერულ მეცნიერებებში Pushdown Automata(PDA) არის მანქანის ისეთი ტიპი, რომელიც იყენებს სტეკს. PDA გამოიყენება ისეთ თეორიებში, რომელიც გვეუბნება რა შეიძლება დაითვალოს კომპიუტერული მანქანების მეშვეობით. ასეთი მანქანას აქვს მეტი შესაძლებლობები ვიდრე სასრულ მდგომარეობიან მანქანას (finite automata), მაგრამ ნაკლები შეუძლია ვიდრე ტურინგის მანქანას. იმის გამო რომ PDA-ში შემომავალი სტრინგი(Input) აღწერილია ფორმალური გრამატიკული ენით, ის შეიძლება გამოვიყენოთ parser-ის დიზაინში. დეტერმინისტულ PDA-ს არ შეუძლია განმარტოს ყველა დეტერმინისტული context-free ენა, მაშინ როდესაც არადეტერმინისტულ PDA-ს შეუძლია განმარტოს ყველა context-free ენა. სტეკის მქონე მანქანას შეუძლია გადაწყვიტოს ენათა უფრო დიდი სიმრავლე ვიდრე დეტერმინისტულ PDA-ს. ასევე, არსებობს ჩადგმულ სტეკიანი მანქანები (A nested stack automaton), რომელიც თავის თავში გულისხმობს უფრო კომპლექსურ მანქანას, კერძოდ ისეთს, რომელსაც სტეკში სასრული სიმბოლოების მაგივრად მნიშნელობებად აქვს ქვესტეკები.

ამ სტატიის დარჩენილ ნაწილში აღწერილია არადეტერმინისტული PDA.

ოპერაცია

Pushdown Automata-ს დიაგრამა

PDA-ს და სასრულ მდგომარეობიან მანქანას(finite state automata) აქვს ორი განმასხვავებელი ნიშანი: 1. PDA-ს შეუძლია გამოიყენოს სტეკის პირველი ადგილი, რათა გადაწყვიტოს, რომელი გადაადგილება უნდა აიღოს. 2. PDA-ს შეუძლია სტეკით მანიპულირება, გადაადგილების შესასრულებლად. PDA-ს შეუძლია აირჩიოს გადაადგილება შემომავალი სტრინგის ინდექსირებით, არსებული მდგომარეობით და სტეკის თავში მყოფი სიმბოლოთი. ეს ნიშნავს, რომ ეს სამი პარამეტრი სრულად განსაზღვრავს გადაადგილებას, რომელიც არის არჩეული. სასრული მდგომარეობის მქონე მანქანას(finite state automata) უპირველეს ყოვლისა, უყურებს შემომავალ სტრინგს და ახლანდელ მდგომარეობას: მას არ აქვს სტეკი, რათა გამოიყენოს იგი. PDA-ს დამატებული აქვს სტეკი, როგორც პარამეტრი, რომელიც ეხმარება არჩევანის გაკეთებაში. PDA-ს შეუძლია სტეკით მანიპულირება გადაადგილების შესასრულებლად. სასრული ფორმის მანქანა არჩევს ახალ მდგომარეობას მომდევნო გადაადგილების მეშვეობით. მანიპულაციის დროს მანქანას შეუძლია ამოიღოს კონკრეტული სიმბოლო, რომელიც იმყოფება სტეკის თავში. ასევე, ასეთ მანქანას შეუძლია დააიგნოროს და დატოვოს ისე როგორც არის. მანიპულაციის (ისევე როგორც სტეკის იგნორის) არჩევანი განსაზღვრულია გადაადგილების ცხრილით.

მოცემული შემომავალი სიგნალით, ახლანდელი მგომარეობითა და სტეკის სიმბოლოთი მანქანას შეუძლია გადავიდეს სხვა მდგომარეობაში და მანიპულაცია მოახდინოს სტეკზე (იღებს ან დებს სიმბოლოს). ზოგადად PDA-ს შეუძლია გააკეთოს სხვადასხვა გამოთვლები და მოქმედებები input-ზე. შედეგი არის დეტერმინისტული PDA და ენა ამ სიტყვების არის დეტერმინისტული context-free ენა. თუმცა ყველა context-free ენა არ არის დეტერმინისტული. ამ ყველაფრიდან გამომდინარეობს ის, რომ DPDA (Deterministic PDA) არის უფრო სუსტი ვარიანტი PDA-ს. ასევე მნიშვნელოვანია ისიც, რომ არ არსებობს ალგორითმი, რომელიც მოცემულ PDA-ს გადაიყვანს ექვივალენტურ DPDA-ში(ცხადია, თუკი ასეთი DPDA არსებობს საერთოდ). თუ ჩვენ დავუშვებთ იმას, რომ სასრულ მანქნას ჰქონდეს ორი სტეკი ერთის ნაცვლად, მივიღებთ გაუმჯობესებულ ვარიანტს, რომელიც ექვივალენტური იქნება ტურინგის მანქანის.

დამოკიდებულება წინა მდგომარეობასთან (Backtracking)

როგორც ზემოთ აღვნიშნეთ, არადეტერმინისტულ PDA-ს შეუძლია ერთ მოქმედებაზე მეტის გაკეთება როდესაც რამდენიმე ვარიანტი აქვს. სინამდვილეში ამისთვის საჭიროა, შეიქმნას ახალი მანქანა, რომელიც თავის მხრივ გადაწყვეტს სხვა არჩევანსაც. პრობლემა ის არის, რომ ასეთი მანქანები პრაქტიკაში ხშირად იჭრებიან. ასეთი შემთხვევების იდენტიფიცირება შეიძლება შემდეგნაირად: მანქანის აგების დროს, საჭიროა გამოვცადოთ (გავტესტოთ) ის გრამატიკა, რომელსაც მანქანა იყენებს. ეს შესაძლებლობას გვაძლევს ყველა ასეთ შემთხვევაში გამოვიყენოთ backtracking, რათა გავაუმჯობესოდ წარმადობა.

ფორმალური განსაზღვრება

ჩვენ ვიყენებთ სტანდარტულ განსაზღვრებას: რომელიც აღნიშნავს ანბანში შემომავალ სტრინგებს, ხოლო აღნიშნავს ცარიელ სტრინგს. PDA განისაზღვრება 7 ნაწილისგან. ესენია: $M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F)$

• $\,Q$ არის სასრული სიმრავლე მდგომარეობებისა (states)
• $\,\Sigma$ არის სასრული სიმრავლე, რომელსაც უწოდებენ შემომავალ ანბანი (input alphabet)
• $\,\Gamma$ არის სასრული სიმრავლე, რომელსაც უწოდებენ სტეკის ანბანს (stack alphabet)
• $\,\delta$ არის სასრული ქვესიმრავლე ~ ის, უწოდებენ (transition relation)
• $\,q_{0}\in \,Q$ არის საწყისი მდგომარეობა (starting state)
• $\ Z\in \,\Gamma$ სტეკის საწყისი სიმბოლო(initial stack symbol)
• $F\subseteq Q$ მდგომარეობა, სადაც იღებს მანქანა სტრინგს (accepting states)

ყველა ელემენტი $(p,a,A,q,\alpha )\in \delta$ არის $M$-ის გადასვლა. მას აქვს განსაზღვრული მნიშვნელობა რომ $M$ მდგომარეობაში $p\in Q$ , $a\in \Sigma \cup \{\varepsilon \}$ input-ით , როგორც ყველაზე მნიშვნელოვანი სტეკის სიმბოლო, შესაძლოა წაიკითხოს $a$, შეცვალოს მდგომარეობა $q$-დ, ამოიღოს $A$, ჩანაცვლებით $\alpha \in \Gamma ^{*}$. $(\Sigma \cup \{\varepsilon \})$ გადანაცვლების კომპონენტი გამოიყენება იმის ფორმულირებისთვის, რომ PDA შეუძლია წაიკითხოს შემომავალი სტრინგიდან სიმბოლო, ან დატოვოს input ხელშეუხებელი. ბევრ ტექსტში, გადასვლის დამოკიდებულება არის ჩანაცვლებული შემდეგი ექვივალენტური, ფორმალიზაციით:

• $\,\delta$ არის გადასვლის ფუნქცია, შესაბამებით(mapping) $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$ შევნიშნოთ, რომ სასრული ამ შემთხვევაშ არის აუცილებელი.

მაგალითი

PDA for $\{0^{n}1^{n}\mid n\geq 0\}$ (by final state)

ეს არის ფორმალური განმარტება PDA-ს, რომელიც წყვეტს შემდეგ ენას: $\{0^{n}1^{n}\mid n\geq 0\}$

$M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ p,\ Z,\ F)$, სადაც

$Q=\{p,q,r\}$

$\Sigma =\{0,1\}$

$\Gamma =\{A,Z\}$

$q_{0}=p$

$F=\{r\}$

$\delta$ შედგები შემდეგი 6 ინსტრუქციისგან:

$(p,0,Z,p,AZ)$, $(p,0,A,p,AA)$, $(p,\epsilon ,Z,q,Z)$, $(p,\epsilon ,A,q,A)$, $(q,1,A,q,\epsilon )$, and $(q,\epsilon ,Z,r,Z)$.

სიტყვებით რომ ვთქვათ, $p$ მდგომარეობაში ყოველი სიმბოლო $0$-თვის წავიკითხოთ და ჩავაგდოთ ერთი სიმბოლო $A$ სტეკში. $A$ -ს ჩაგდება სტეკის თავში ზემოდან კიდევ სხვა $A$-ზე, ფორმულირდება როგორც ამ ორის ჩანაცლება $AA$-თი. $q$ მდგომარეობაში ყოველი სიმბოლოსთვის, რომელიც არის $1$-იანი, წავიკითხოთ და ამოვაგდოთ $A$ სტეკიდან. ნებისმიერ მომენტში მანქანა შიძლება გადაადგილდეს $p$-დან $q$ მდგომარეობაში. მაშინ როდესაც სტეკი შეიცავს ერთადერთ სიმბოლოს $Z$-ს, მანქანას შეუძლია გადასვლა $q$-დან მიმღებ მდგომარეობაშ $r$(accepting state).

გამოანგარიშების პროცესები

მისაღები გამოთვლა $0011$-თვის

ქვემოთ აღწერილია, როგორ ხდება სხვადასხვა Input-ის გამოთვლა PDA-თი. ა) შემავალი სტრინგი = 0011. გვაქვს გამოთვლის სხვადასხვა ვარიანტი, რომელიც დამოკიდებულია გადასვლაზე $p$ მდგომარეობიდან $q$ მდგომარეობაში. თუმცა, მხოლოდ ერთი იღებს ამ სტრინგს, ანუ არის მიმღები მდგომარეობა (accepting states).

(i) $(p,0011,Z)\vdash (q,0011,Z)\vdash (r,0011,Z)$ ფინალური მდგომარეობა იღებს, მაგრამ input ამ შემთხვევაში არ მიიღება, რადგან ის არ კითხულობს.

(ii) $(p,0011,Z)\vdash (p,011,AZ)\vdash (q,011,AZ)$ არ არის სხვა შესაძლო ვარიანტი.

(iii) $(p,0011,Z)\vdash (p,011,AZ)\vdash (p,11,AAZ)\vdash (q,11,AAZ)$ $\vdash (q,1,AZ)\vdash (q,\epsilon ,Z)$ $\vdash (r,\epsilon ,Z)$ მთავრდება მიმღებ მდგომარეობაში, როდესაც დასრულდება input-ის წაკითხვა.

ბ) შემომავალი სტრინგი = 00111. ასევე არის სხვადასხვა ვარიანტი გამოთვლის, თუმცა, არც ერთი არ იღებს შემომავალ სტრინგს

(i) $(p,00111,Z)\vdash (q,00111,Z)\vdash (r,00111,Z)$ საბოლოო მდგომარეობა იღებს, მაგრამ input არაა ბოლომდე წაკითხული

(ii) $(p,00111,Z)\vdash (p,0111,AZ)\vdash (q,0111,AZ)$ არ არის სხვა შესაძლო ვარიანტი

(iii) $(p,00111,Z)\vdash (p,0111,AZ)\vdash (p,111,AAZ)\vdash (q,111,AAZ)$ $\vdash (q,11,AZ)\vdash (q,1,Z)$ $\vdash (r,1,Z)$ მართალია, საბოლოო მდგომარეობა იღებს input-ს, მაგრამ ეს ის შემთხვევაა, როდესაც არ შეიძლება ვთქვათ, რომ input მიიღო, რადგან შემავალი სტრინგი არ არის ბოლომდე წაკითხული.

განზოგადებული PDA (GPDA)

(GPDA) არის PDA, რომელიც წერს შემომავალი სტრინგის (ცნობილია სიგრძე) სტეკში და ასევე შლის მას სტეკიდან ერთ ბიჯზე.

(GPDA) განიმარტება შემდეგნაირად:

$M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ F)$

სადაც Q, $\Sigma \,$, $\Gamma \,$, q₀ არის განსაზღვრული როგორც PDA.

$\,\delta$: $Q\times \Sigma _{\epsilon }\times \Gamma ^{*}\longrightarrow P(Q\times \Gamma ^{*})$

არის ტრანზაციის ფუნქცია. გამოთვლითი წესები GPDA-სთვის არის მსგავსად PDA-სი, განსხვავებით იმისა, რომ ai+1 და bi+1 არიან სტრინგები განსხვავებით სიმბოლოსი. GPDA და PDA არიამ ექვივალენტები, იმიტომ რომ თუ ენა გადაწყვეტადია PDA-თი, მაშინ ასევე ეს ენა გადაწყდება აუცილებლად GPDA-ითაც. დავამტკიცოთ, რომ GPDA და PDA არიან ექვივალენტურები: ვთქვათ, $\delta$(q₁, w, x₁x₂...x_m) $\longrightarrow$ (q₂, y₁y₂...y_n არის GPDA-ს გადასვლა, სადაც $q_{1},q_{2}\in Q$, $w\in \Sigma _{\epsilon }$, $x_{1},x_{2},\ldots ,x_{m}\in \Gamma ^{*}$, $m\geq 0$, $y_{1},y_{2},\ldots ,y_{n}\in \Gamma ^{*}$, $n\geq 0$.

ავაგოთ შესაბამისი PDA:

$\delta ^{'}$(q₁, w, x₁) $\longrightarrow$ (p₁, $\epsilon$)

$\delta ^{'}$(p₁, $\epsilon$, x₂) $\longrightarrow$ (p₂, $\epsilon$)

$\vdots$

$\delta ^{'}$(p_m-1, $\epsilon$, x_m) $\longrightarrow$ (p_m, $\epsilon$)

$\delta ^{'}$(p_m, $\epsilon$, $\epsilon$ ) $\longrightarrow$ (p_m+1, y_n)

$\delta ^{'}$(p_m+1, $\epsilon$, $\epsilon$ ) $\longrightarrow$ (p_m+2, y_n-1)

$\vdots$

$\delta ^{'}$(p_m+n-1, $\epsilon$, $\epsilon$ ) $\longrightarrow$ (q₂, y₁)