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

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 \})$ घटक का उपयोग यह औपचारिक बनाने के लिए किया जाता है कि पीडीए या तो इनपुट से पत्र पढ़ सकता है, या इनपुट को अछूता छोड़कर आगे बढ़ सकता है।

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

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

यहाँ $\delta (p,a,A)$ में इनपुट पर $a$ पढ़ते समय स्टैक पर $A$ की स्थिति $p$ में सभी संभावित क्रियाएं सम्मिलित हैं। उदाहरण के लिए कोई $\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$ तात्कालिक विवरण पर $M$ के चरण-संबंध $\vdash _{M}$ को परिभाषित करता है। निर्देश$(p,a,A,q,\alpha )\in \delta$ के लिए प्रत्येक $x\in \Sigma ^{*}$ और प्रत्येक $\gamma \in \Gamma ^{*}$ के लिए एक चरण $(p,ax,A\gamma )\vdash _{M}(q,x,\alpha \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 द्वारा प्रतिस्थापित करने के रूप में औपचारिक रूप दिया जाता है (और इसी प्रकार Z के शीर्ष पर प्रतीक A को पुश करने के लिए)।

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

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

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

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

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

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

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

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. प्रत्येक नियम $A\to \alpha$ के लिए $(1,\varepsilon ,A,1,\alpha )$ (विस्तृत करें)
2. प्रत्येक टर्मिनल प्रतीक $a$ के लिए $(1,a,a,1,\varepsilon )$ (मैच)

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

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

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

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

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

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

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

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

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

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

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

जीपीडीए को औपचारिक रूप से 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})$ जीपीडीए का परिवर्तन हो

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

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

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

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

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

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

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

यह भी देखें

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

संदर्भ

• 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)