पुशडाउन ऑटोमेटन

Classes of automata

गणना के सिद्धांत में, सैद्धांतिक कंप्यूटर विज्ञान की शाखा, पुशडाउन ऑटोमेटन (पीडीए) है एक प्रकार का ऑटोमेटा सिद्धांत जो एक स्टैक (डेटा संरचना) को नियोजित करता है।

मशीनों द्वारा क्या गणना की जा सकती है, इसके सिद्धांतों में पुशडाउन ऑटोमेटा का उपयोग किया जाता है। वे परिमित-स्थिति मशीनों की तुलना में अधिक सक्षम हैं परन्तु ट्यूरिंग मशीनों की तुलना में कम सक्षम हैं ( पीडीए और ट्यूरिंग मशीनें देखें)।

डीटरमिनिस्ट पुशडाउन ऑटोमेटा सभी डीटरमिनिस्ट डीटरमिनिस्ट कॉन्टेक्स्ट-फ्री लैंग्वेज को पहचान सकता है जबकि गैर-डीटरमिनिस्ट कॉन्टेक्स्ट-फ्री लैंग्वेज लैंग्वेज को पहचान सकता है, पूर्व का उपयोग प्रायः पार्सर डिज़ाइन में किया जाता है।

पुशडाउन शब्द इस तथ्य को संदर्भित करता है कि स्टैक (अमूर्त डेटा प्रकार) को कैफेटेरिया में ट्रे डिस्पेंसर के जैसे नीचे पुशडाउन के रूप में माना जा सकता है, क्योंकि ऑपरेशन कभी भी शीर्ष अवयव के अतिरिक्त अन्य अवयवों पर कार्य नहीं करते हैं। इसके विपरीत, स्टैक ऑटोमेटन, गहन अवयवों तक एक्सेस और ऑपरेशन की अनुमति देता है। स्टैक ऑटोमेटा पुशडाउन ऑटोमेटा की तुलना में लैंग्वेज के बड़े समूह को पहचान सकता है। एक नेस्टेड स्टैक ऑटोमेटन पूर्ण एक्सेस की अनुमति देता है, और स्टैक्ड मानों को मात्र एकल परिमित प्रतीकों के अतिरिक्त संपूर्ण उप-स्टैक होने की भी अनुमति देता है।

अनौपचारिक विवरण

पुशडाउन ऑटोमेटन का आरेख

एक परिमित-स्थिति मशीन मात्र इनपुट सिग्नल और वर्तमान स्थिति को देखती है: इसके निकट कार्य करने के लिए कोई स्टैक नहीं है। यह नवीन स्थिति चुनता है, जो परिवर्तन का अनुसरण करने का परिणाम है। पुशडाउन ऑटोमेटन (पीडीए) परिमित स्थिति मशीन से दो विधियों से भिन्न होता है:

1. यह स्टैक के शीर्ष का उपयोग यह निर्धारित करने के लिए कर सकता है कि कौन सा ट्रांजीशन लेना है।
2. यह ट्रांजीशन निष्पादित करने के भाग के रूप में स्टैक में परिवर्तन कर सकता है।

एक पुशडाउन ऑटोमेटन किसी दिए गए इनपुट स्ट्रिंग को बाएं से दाएं पढ़ता है। प्रत्येक चरण में, यह इनपुट प्रतीक, वर्तमान स्थिति और स्टैक के शीर्ष पर प्रतीक द्वारा तालिका को अनुक्रमित करके ट्रांजीशन चुनता है। ट्रांज़िशन निष्पादित करने के भाग के रूप में, पुशडाउन ऑटोमेटन स्टैक में परिवर्तन भी कर सकता है। परिवर्तन किसी विशेष प्रतीक को स्टैक के शीर्ष पर पुशडाउन या स्टैक के शीर्ष को पॉप करने के लिए हो सकता है। ऑटोमेटन वैकल्पिक रूप से स्टैक को अनदेखा कर सकता है, और इसे वैसे ही छोड़ सकता है। एक साथ रखें: इनपुट प्रतीक, वर्तमान स्थिति और स्टैक प्रतीक को देखते हुए, ऑटोमेटन किसी अन्य स्थिति में ट्रांजीशन का पालन कर सकता है, और वैकल्पिक रूप से स्टैक में परिवर्तन (पुश या पॉप) कर सकता है।

यदि, प्रत्येक स्थिति में, अधिकतम ऐसी संक्रमण क्रिया संभव है, तो ऑटोमेटन को डीटरमिनिस्ट पुशडाउन ऑटोमेटन (डीपीडीए) कहा जाता है। सामान्यतः, यदि कई क्रियाएं संभव हैं, तो ऑटोमेटन को सामान्य, या गैर-डीटरमिनिस्ट, पीडीए कहा जाता है। दी गई इनपुट स्ट्रिंग गैर-डीटरमिनिस्ट पुशडाउन ऑटोमेटन को कई कॉन्फ़िगरेशन अनुक्रमों में से एक में चला सकती है; यदि उनमें से पूर्ण इनपुट स्ट्रिंग को पढ़ने के बाद स्वीकार्य कॉन्फ़िगरेशन की ओर ले जाता है, तो बाद वाले को ऑटोमेटन द्वारा स्वीकृत लैंग्वेज से संबंधित माना जाता है।

संक्रमण संबंध

• $q_{0}\in Q$ आरंभिक अवस्था है
• $Z\in \Gamma$ प्रारंभिक स्टैक प्रतीक है
• $F\subseteq Q$ स्वीकार करने वाले स्थितिों का समूह है

एक अवयव $(p,a,A,q,\alpha )\in \delta$, $M$ का संक्रमण है । इसका अभिप्राय यह है कि $M$, स्थिति $p\in Q$ में, इनपुट $a\in \Sigma \cup \{\varepsilon \}$ पर और $A\in \Gamma$ को सबसे ऊपरी स्टैक प्रतीक के रूप में, $a$ के रूप में पढ़ सकता है, स्थिति को $q$ में बदल सकता है, पॉप $A$ पॉप कर सकता है, इसे $\alpha \in \Gamma ^{*}$ दबाकर प्रतिस्थापित कर सकता है। $(\Sigma \cup \{\varepsilon \})$ h> संक्रमण संबंध के घटक का उपयोग यह औपचारिक बनाने के लिए किया जाता है कि पीडीए या तो इनपुट से पत्र पढ़ सकता है, या इनपुट को अछूता छोड़कर आगे बढ़ सकता है।

अनेक ग्रंथों में संक्रमण संबंध को (समतुल्य) औपचारिकता द्वारा प्रतिस्थापित किया जाता है, जहां

• $\delta$ संक्रमण फ़ंक्शन, मैपिंग है $Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma$ के परिमित उपसमुच्चय में $Q\times \Gamma ^{*}$

यहाँ $\delta (p,a,A)$ स्थिति में सभी संभावित कार्रवाइयां शामिल हैं $p$ साथ $A$ पढ़ते समय, स्टैक पर $a$ इनपुट पर। उदाहरण के लिए कोई लिखता है $\delta (p,a,A)=\{(q,BA)\}$ बिल्कुल कब $(q,BA)\in \{(q,BA)\},(q,BA)\in \delta (p,a,A),$ क्योंकि $((p,a,A),\{(q,BA)\})\in \delta$। ध्यान दें कि इस परिलैंग्वेज में परिमित आवश्यक है।

'गणना'

पुशडाउन ऑटोमेटन का चरण

पुशडाउन ऑटोमेटन के शब्दार्थ को औपचारिक बनाने के लिए वर्तमान स्थिति का विवरण प्रस्तुत किया गया है। कोई भी 3-टुपल $(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$), जिसका अर्थ है कि इसके इनपुट को पढ़ने के बाद ऑटोमेटन अपना स्टैक खाली कर देता है। पहला स्वीकृति मोड आंतरिक मेमोरी (स्थिति) का उपयोग करता है, दूसरा बाहरी मेमोरी (स्टैक) का।

औपचारिक रूप से कोई परिभाषित करता है

1. $L(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(f,\varepsilon ,\gamma )$ साथ $f\in F$ और $\gamma \in \Gamma ^{*}\}$ (अंतिम स्थिति)
2. $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')$

उदाहरण

निम्नलिखित पीडीए का औपचारिक विवरण है जो लैंग्वेज को पहचानता है $\{0^{n}1^{n}\mid n\geq 0\}$ अंतिम स्थिति के अनुसार:

के लिए पीडीए $\{0^{n}1^{n}\mid n\geq 0\}$
(अंतिम स्थिति के अनुसार)

$M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F)$, कहाँ

• बताता है: $Q=\{p,q,r\}$
• इनपुट वर्णमाला: $\Sigma =\{0,1\}$
• स्टैक वर्णमाला: $\Gamma =\{A,Z\}$
• प्रारंभ स्थिति: $q_{0}=p$
• स्टार्ट स्टैक प्रतीक: Z
• स्वीकार करने की स्थिति: $F=\{r\}$

संक्रमण संबंध $\delta$ निम्नलिखित छह निर्देश शामिल हैं:

$(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 )$, और

$(q,\epsilon ,Z,r,Z)$।

शब्दों में, पहले दो निर्देश कहते हैं कि स्थिति में p किसी भी समय प्रतीक 0 पढ़ा जाता है, A को स्टैक पर पुशडाउन किया जाता है। धक्का देने वाला प्रतीक A दूसरे के ऊपर A को शीर्ष के स्थान पर औपचारिक रूप दिया गया है A द्वारा AA (और इसी प्रकार प्रतीक को आगे बढ़ाने के लिए Aए के शीर्ष पर Z)।

तीसरे और चौथे निर्देश कहते हैं कि, किसी भी क्षण ऑटोमेटन स्थिति से हट सकता है p कहना q।

पांचवां निर्देश कहता है कि स्थिति में q, प्रत्येक प्रतीक के लिए 1 पढ़ें, A पॉप हो गया है।

अंत में, छठा निर्देश कहता है कि मशीन स्थिति से आगे बढ़ सकती है q स्थिति को स्वीकार करने के लिए r मात्र तभी जब स्टैक में एकल शामिल हो Z।

ऐसा लगता है कि पीडीए के लिए आम तौर पर इस्तेमाल किया जाने वाला कोई प्रतिनिधित्व नहीं है। यहां हमने निर्देश दर्शाया है $(p,a,A,q,\alpha )$ स्थिति से बढ़त से p कहना q द्वारा लेबल किया गया $a;A/\alpha$ (पढ़ना a; बदलना A द्वारा $\alpha$)।

गणना प्रक्रिया को समझना

के लिए गणना स्वीकार करना 0011

निम्नलिखित दर्शाता है कि उपरोक्त पीडीए विभिन्न इनपुट स्ट्रिंग्स पर कैसे गणना करता है। सबस्क्रिप्ट M चरण चिह्न से $\vdash$ यहाँ छोड़ दिया गया है।

1. Input string = 0011. There are various computations, depending on the moment the move from state p to state q is made. Only one of these is accepting.
   1. $(p,0011,Z)\vdash (q,0011,Z)\vdash (r,0011,Z)$
      The final state is accepting, but the input is not accepted this way as it has not been read.
   2. $(p,0011,Z)\vdash (p,011,AZ)\vdash (q,011,AZ)$
      No further steps possible.
   3. $(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)$
      Accepting computation: ends in accepting state, while complete input has been read.
2. Input string = 00111. Again there are various computations. None of these is accepting.
   1. $(p,00111,Z)\vdash (q,00111,Z)\vdash (r,00111,Z)$
      The final state is accepting, but the input is not accepted this way as it has not been read.
   2. $(p,00111,Z)\vdash (p,0111,AZ)\vdash (q,0111,AZ)$
      No further steps possible.
   3. $(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)$
      The final state is accepting, but the input is not accepted this way as it has not been (completely) read.

पीडीए और संदर्भ-मुक्त लैंग्वेज

प्रत्येक संदर्भ-मुक्त व्याकरण को समतुल्य गैर-डीटरमिनिस्ट पुशडाउन ऑटोमेटन में परिवर्तित किया जा सकता है। व्याकरण की व्युत्पत्ति प्रक्रिया को सबसे बाएं तरीके से अनुकरण किया जाता है। जहां व्याकरण नॉनटर्मिनल को फिर से लिखता है, पीडीए अपने स्टैक से सबसे ऊपरी नॉनटर्मिनल लेता है और इसे व्याकरणिक नियम (विस्तार) के दाहिने हाथ के हिस्से से बदल देता है। जहां व्याकरण टर्मिनल प्रतीक उत्पन्न करता है, पीडीए इनपुट से प्रतीक पढ़ता है जब यह स्टैक (मैच) पर सबसे ऊपरी प्रतीक होता है। अर्थ में पीडीए के स्टैक में व्याकरण का असंसाधित डेटा होता है, जो व्युत्पत्ति वृक्ष के प्री-ऑर्डर ट्रैवर्सल के अनुरूप होता है।

तकनीकी रूप से, संदर्भ-मुक्त व्याकरण को देखते हुए, पीडीए की ही स्थिति है, 1, और इसका संक्रमण संबंध इस प्रकार बनाया गया है।

1. $(1,\varepsilon ,A,1,\alpha )$ प्रत्येक नियम के लिए $A\to \alpha$ (बढ़ाना)
2. $(1,a,a,1,\varepsilon )$ प्रत्येक टर्मिनल प्रतीक के लिए $a$ (मिलान)

पीडीए खाली स्टैक द्वारा स्वीकार करता है। इसका प्रारंभिक स्टैक प्रतीक व्याकरण का प्रारंभ प्रतीक है।

ग्रीबैक सामान्य रूप में संदर्भ-मुक्त व्याकरण के लिए, प्रत्येक व्याकरण नियम ए → एγ के लिए (1,γ) ∈ δ(1,a,A) को परिभाषित करने से समतुल्य गैर-डीटरमिनिस्ट पुशडाउन ऑटोमेटन भी प्राप्त होता है।

किसी दिए गए पीडीए के लिए व्याकरण ढूंढना इतना आसान नहीं है। चाल पीडीए के दो स्थितिों को व्याकरण के गैर-टर्मिनलों में कोड करने की है।

प्रमेय। प्रत्येक पुशडाउन ऑटोमेटन के लिए $M$ कोई संदर्भ-मुक्त व्याकरण का निर्माण कर सकता है $G$ ऐसा है कि $N(M)=L(G)$.

डीटरमिनिस्ट पुशडाउन ऑटोमेटन (डीपीडीए) द्वारा स्वीकृत स्ट्रिंग्स की लैंग्वेज को डीटरमिनिस्ट संदर्भ-मुक्त लैंग्वेज कहा जाता है। सभी संदर्भ-मुक्त लैंग्वेज नियतिवादी नहीं हैं।परिणामस्वरूप, डीपीडीए पीडीए का सख्ती से कमजोर संस्करण है। यहां तक ​​कि नियमित लैंग्वेज के लिए भी, आकार विस्फोट की समस्या है: किसी भी सामान्य पुनरावर्ती फ़ंक्शन के लिए $f$ और मनमाने ढंग से बड़े पूर्णांकों के लिए $n$, आकार का पीडीए है $n$ नियमित लैंग्वेज का वर्णन करना जिसकी सबसे छोटी डीपीडीए के निकट कम से कम है $f(n)$ स्थिति। कई गैर-नियमित पीडीए के लिए, किसी भी समकक्ष डीपीडीए को असीमित संख्या में स्थितिों की आवश्यकता होगी।

दो स्टैक तक एक्सेस वाला सीमित ऑटोमेटन अधिक शक्तिशाली उपकरण है, जो ट्यूरिंग मशीन की शक्ति के बराबर है। रैखिक परिबद्ध ऑटोमेटन उपकरण है जो पुशडाउन ऑटोमेटन से अधिक शक्तिशाली है परन्तु ट्यूरिंग मशीन से कम शक्तिशाली है।

पीडीए और ट्यूरिंग मशीनें

एक पुशडाउन ऑटोमेटन कम्प्यूटेशनल रूप से दो टेपों के साथ 'प्रतिबंधित' ट्यूरिंग मशीन (टीएम) के बराबर है जो निम्नलिखित तरीके से प्रतिबंधित है- पहले टेप पर, टीएम मात्र इनपुट पढ़ सकता है और बाएं से दाएं जा सकता है (यह परिवर्तन नहीं कर सकता)। दूसरे टेप पर, यह मात्र डेटा को 'पुश' और 'पॉप' कर सकता है। या समकक्ष, यह पढ़ सकता है, लिख सकता है और बाएँ और दाएँ घूम सकता है, इस प्रतिबंध के साथ कि यह प्रत्येक चरण में मात्र ही कार्य कर सकता है या तो स्ट्रिंग (पॉप) में सबसे बाएँ वर्ण को हटाना है या स्ट्रिंग (पुश) में सबसे बाएँ वर्ण के बाएँ अतिरिक्त वर्ण जोड़ना है।

पीडीए टीएम से कमजोर है, इसे इस तथ्य से समझा जा सकता है कि प्रक्रिया 'पॉप' कुछ डेटा को हटा देती है। पीडीए को टीएम जितना मजबूत बनाने के लिए, हमें 'पॉप' के माध्यम से खोए गए डेटा को कहीं सहेजना होगा। हम दूसरा स्टैक शुरू करके इसे हासिल कर सकते हैं। अंतिम पैराग्राफ के पीडीए के टीएम मॉडल में, यह 3 टेप वाले टीएम के बराबर है, जहां पहला टेप मात्र-पढ़ने के लिए इनपुट टेप है, और दूसरा और तीसरा टेप 'पुश और पॉप' (स्टैक) टेप हैं। ऐसे पीडीए के लिए किसी दिए गए टीएम का अनुकरण करने के लिए, हम दोनों स्टैक को खाली रखते हुए, पहले टेप में पीडीए का इनपुट देते हैं। इसके बाद यह इनपुट टेप से सभी इनपुट को पहले स्टैक तक पुशडाउन करता है। जब संपूर्ण इनपुट को पहले स्टैक में स्थानांतरित कर दिया जाता है, तो अब हम सामान्य टीएम के जैसे आगे बढ़ते हैं, जहां टेप पर दाईं ओर जाना पहले स्टैक से प्रतीक को पॉप करने और दूसरे स्टैक में (संभवतः अपडेट किए गए) प्रतीक को पुशडाउन के समान है, और बाईं ओर जाने से दूसरे स्टैक से प्रतीक को पॉप करने और (संभवतः अपडेट किए गए) प्रतीक को पहले स्टैक में पुशडाउन के समान होता है। इसलिए हमारे निकट 2 स्टैक वाला पीडीए है जो किसी भी टीएम का अनुकरण कर सकता है।

सामान्यीकृत पुशडाउन ऑटोमेटन (जीपीडीए)

जीपीडीए पीडीए है जो स्टैक पर कुछ ज्ञात लंबाई की पूर्ण स्ट्रिंग लिखता है या चरण में स्टैक से पूर्ण स्ट्रिंग को हटा देता है।

GPDA को औपचारिक रूप से 6-टुपल के रूप में परिभाषित किया गया है:

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

कहाँ $Q,\Sigma \,,\Gamma \,,q_{0}$, और $F$ को पीडीए के जैसे ही परिभाषित किया गया है।

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

संक्रमण फलन है।

जीपीडीए के लिए गणना नियम पीडीए के समान हैं, सिवाय इसके कि $a_{i+1}$'रेत $b_{i+1}$अब प्रतीकों के अतिरिक्त तार हैं।

जीपीडीए और पीडीए इस मायने में समतुल्य हैं कि यदि कोई लैंग्वेज पीडीए द्वारा मान्यता प्राप्त है, तो इसे जीपीडीए द्वारा भी मान्यता प्राप्त है और इसके विपरीत भी।

निम्नलिखित सिमुलेशन का उपयोग करके जीपीडीए और पीडीए की तुल्यता के लिए विश्लेषणात्मक प्रमाण तैयार किया जा सकता है:

होने देना $\delta (q_{1},w,x_{1}x_{2}\cdot x_{m})\longrightarrow (q_{2},y_{1}y_{2}...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$।

पीडीए के लिए निम्नलिखित बदलावों का निर्माण करें:

${\begin{array}{lcl}\delta '(q_{1},w,x_{1})&\longrightarrow &(p_{1},\epsilon )\\\delta '(p_{1},\epsilon ,x_{2})&\longrightarrow &(p_{2},\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_{2},y_{1}).\end{array}}$

स्टैक ऑटोमेटन

पुशडाउन ऑटोमेटा के सामान्यीकरण के रूप में, गिंसबर्ग, ग्रीबैक और हैरिसन (1967) ने स्टैक ऑटोमेटा की जांच की, जो अतिरिक्त रूप से इनपुट स्ट्रिंग में बाएं या दाएं कदम रख सकता है (बाहर फिसलने से रोकने के लिए विशेष एंडमार्कर प्रतीकों से घिरा हुआ), और ऊपर या नीचे कदम रख सकता है मात्र-पढ़ने योग्य मोड में स्टैक करें। स्टैक ऑटोमेटन को नॉनरेज़िंग कहा जाता है यदि यह स्टैक से कभी नहीं निकलता है। नॉनडेटर्मिनिस्टिक, नॉनरेज़िंग स्टैक ऑटोमेटा द्वारा स्वीकृत लैंग्वेज का वर्ग NSPACE(n) है²), जो संदर्भ-संवेदनशील लैंग्वेज#कम्प्यूटेशनल गुणों|संदर्भ-संवेदनशील लैंग्वेज का सुपरसेट है। डीटरमिनिस्ट, नॉनरेज़िंग स्टैक ऑटोमेटा द्वारा स्वीकृत लैंग्वेज का वर्ग DSPACE(n⋅log(n)) है।

वैकल्पिक पुशडाउन ऑटोमेटा

एक वैकल्पिक पुशडाउन ऑटोमेटन (एपीडीए) स्थिति सेट के साथ पुशडाउन ऑटोमेटन है

• $Q=Q_{\exists }\cup Q_{\forall }$ कहाँ $Q_{\exists }\cap Q_{\forall }=\emptyset$।

स्थितिों में $Q_{\exists }$ और $Q_{\forall }$ अस्तित्वगत सम्मान कहलाते हैं। सार्वभौमिक। अस्तित्वगत स्थिति में एपीडीए गैर-डीटरमिनिस्ट रूप से अगले स्थिति को चुनता है और स्वीकार करता है यदि परिणामी गणनाओं में से कम से कम स्वीकार करता है। सार्वभौमिक स्थिति में APDA सभी अगले स्थितिों में चला जाता है और यदि सभी परिणामी गणनाएँ स्वीकार हो जाती हैं तो स्वीकार करता है।

मॉडल को अशोक के। चंद्रा, डेक्सटर कोज़ेन और लैरी स्टॉकमेयर द्वारा पेश किया गया था। रिचर्ड ई। लैडनर, रिचर्ड जे। लिप्टन और लैरी स्टॉकमेयर साबित हुआ कि यह मॉडल EXPTIME के ​​बराबर है यानी लैंग्वेज कुछ APDA द्वारा स्वीकार की जाती है यदि, और मात्र तभी, इसे घातीय-समय एल्गोरिदम द्वारा निर्धारित किया जा सकता है।

ऐज़िकोविट्ज़ और कमिंसकी सिंक्रोनाइज्ड अल्टरनेटिंग पुशडाउन ऑटोमेटा (एसएपीडीए) पेश किया गया जो कि संयोजक व्याकरण के समतुल्य है, उसी प्रकार जैसे गैर-डीटरमिनिस्ट पीडीए संदर्भ-मुक्त व्याकरण के समतुल्य है।

यह भी देखें

• स्टैक मशीन
• प्रसंग-मुक्त व्याकरण
• परिमित स्वचालन
• काउंटर ऑटोमेटन
• कतार स्वचालित

संदर्भ

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 2।2: Pushdown Automata, pp। 101–114।
• Jean-Michel Autebert, Jean Berstel, Luc Boasson, Context-Free लैंग्वेजs and Push-Down Automata, in: G। Rozenberg, A। Salomaa (eds।), Handbook of Formal लैंग्वेजs, Vol। 1, Springer-Verlag, 1997, 111–174।

बाहरी संबंध

• JFLAP, simulator for several types of automata including nondeterministic pushdown automata
• CoAn, another simulator for several machine types including nondeterministic pushdown automata (C++, Windows, Linux, MacOS)