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

Classes of automata

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

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

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

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

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

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

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

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

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

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

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

नियतात्मक पुशडाउन ऑटोमेटन (DPDA) द्वारा स्वीकृत स्ट्रिंग्स की भाषा को नियतात्मक संदर्भ-मुक्त भाषा कहा जाता है। सभी संदर्भ-मुक्त भाषाएँ नियतिवादी नहीं हैं।परिणामस्वरूप, डीपीडीए पीडीए का एक सख्ती से कमजोर संस्करण है। यहां तक ​​कि नियमित भाषाओं के लिए भी, आकार विस्फोट की समस्या है: किसी भी सामान्य पुनरावर्ती फ़ंक्शन के लिए $f$ और मनमाने ढंग से बड़े पूर्णांकों के लिए $n$, आकार का एक पीडीए है $n$ एक नियमित भाषा का वर्णन करना जिसकी सबसे छोटी DPDA के पास कम से कम है $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 Languages and Push-Down Automata, in: G. Rozenberg, A. Salomaa (eds.), Handbook of Formal Languages, 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)