पुशडाउन ऑटोमेटन: Difference between revisions

Revision as of 00:10, 26 July 2023

Classes of automata

(Clicking on each layer gets an article on that subject)

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

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

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

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

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

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

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

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

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

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

ट्रांजीशन संबंध

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

अनेक ग्रंथों में^[2]^: 110 ट्रांजीशन संबंध को (समतुल्य) औपचारिकता द्वारा प्रतिस्थापित किया जाता है, जहां

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

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

$L(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(f,\varepsilon ,\gamma )$ साथ $f\in F$ और $\gamma \in \Gamma ^{*}\}$ (अंतिम स्थिति)
$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$ यहाँ छोड़ दिया गया है.

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.
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,\varepsilon ,A,1,\alpha )$ प्रत्येक नियम के लिए $A\to \alpha$ (बढ़ाना)
$(1,a,a,1,\varepsilon )$ प्रत्येक टर्मिनल प्रतीक के लिए $a$ (मिलान)

पीडीए खाली स्टैक द्वारा स्वीकार करता है। इसका प्रारंभिक स्टैक प्रतीक व्याकरण का प्रारंभ प्रतीक है।^{[citation needed]}

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

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

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

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

दो स्टैक तक एक्सेस वाला सीमित ऑटोमेटन अधिक शक्तिशाली उपकरण है, जो ट्यूरिंग मशीन की शक्ति के बराबर है।^[2]^: 171 रैखिक परिबद्ध ऑटोमेटन उपकरण है जो पुशडाउन ऑटोमेटन से अधिक शक्तिशाली है परन्तु ट्यूरिंग मशीन से कम शक्तिशाली है।^{[note 1]}

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

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

पीडीए टीएम से कमजोर है, इसे इस तथ्य से समझा जा सकता है कि प्रक्रिया 'पॉप' कुछ डेटा को हटा देती है। पीडीए को टीएम जितना मजबूत बनाने के लिए, हमें 'पॉप' के माध्यम से खोए गए डेटा को कहीं सहेजना होगा। हम दूसरा स्टैक शुरू करके इसे हासिल कर सकते हैं। अंतिम पैराग्राफ के पीडीए के टीएम मॉडल में, यह 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) ने स्टैक ऑटोमेटा की जांच की, जो अतिरिक्त रूप से इनपुट स्ट्रिंग में बाएं या दाएं कदम रख सकता है (बाहर फिसलने से रोकने के लिए विशेष एंडमार्कर प्रतीकों से घिरा हुआ), और ऊपर या नीचे कदम रख सकता है मात्र-पढ़ने योग्य मोड में स्टैक करें।^[4]^[5] स्टैक ऑटोमेटन को नॉनरेज़िंग कहा जाता है यदि यह स्टैक से कभी नहीं निकलता है। नॉनडेटर्मिनिस्टिक, नॉनरेज़िंग स्टैक ऑटोमेटा द्वारा स्वीकृत लैंग्वेज का वर्ग NSPACE(n) है²), जो संदर्भ-संवेदनशील लैंग्वेज#कम्प्यूटेशनल गुणों|संदर्भ-संवेदनशील लैंग्वेज का सुपरसेट है।^[1] डीटरमिनिस्ट, नॉनरेज़िंग स्टैक ऑटोमेटा द्वारा स्वीकृत लैंग्वेज का वर्ग DSPACE(n⋅log(n)) है।^[1]

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

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

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

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

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

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

यह भी देखें

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

संदर्भ

↑ ^1.0 ^1.1 ^1.2 John E. Hopcroft; Jeffrey D. Ullman (1967). "नॉनरेज़िंग स्टैक ऑटोमेटा". Journal of Computer and System Sciences. 1 (2): 166–186. doi:10.1016/s0022-0000(67)80013-8.
↑ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 John E. Hopcroft and Jeffrey D. Ullman (1979). ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X.
↑ Holzer, Markus; Kutrib, Martin (2019). "Non-Recursive Trade-Offs Are "Almost Everywhere"". Computing with Foresight and Industry. 11558: 25–36. doi:10.1007/978-3-030-22996-2_3. This follows from the quoted [22, Proposition 7] and the stated observation that any deterministic pushdown automaton can be converted into an equivalent finite automaton^[clarify] of at most doubly-exponential size.
↑ Seymour Ginsburg, Sheila A. Greibach and Michael A. Harrison (1967). "स्टैक ऑटोमेटा और संकलन". J. ACM. 14 (1): 172–201. doi:10.1145/321371.321385.
↑ Seymour Ginsburg, Sheila A. Greibach and Michael A. Harrison (1967). "वन-वे स्टैक ऑटोमेटा". J. ACM. 14 (2): 389–418. doi:10.1145/321386.321403.
↑ Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "अदल-बदल". Journal of the ACM. 28 (1): 114–133. doi:10.1145/322234.322243. ISSN 0004-5411.
↑ Ladner, Richard E.; Lipton, Richard J.; Stockmeyer, Larry J. (1984). "वैकल्पिक पुशडाउन और स्टैक ऑटोमेटा". SIAM Journal on Computing. 13 (1): 135–155. doi:10.1137/0213010. ISSN 0097-5397.
↑ Aizikowitz, Tamar; Kaminski, Michael (2011). "LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata". Computer Science – Theory and Applications. Lecture Notes in Computer Science. Vol. 6651. pp. 345–358. doi:10.1007/978-3-642-20712-9_27. ISBN 978-3-642-20711-2. ISSN 0302-9743.

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)

[4] Linear bounded automata are acceptors for the class of context-sensitive languages,^[2]^: 225 which is a proper superclass of the context-free languages, and a proper subclass of Turing-recognizable (i.e. recursively enumerable) languages.^[2]^: 228

[Hopcroft.Ullman.1967-1] 1.0 ^1.1 ^1.2 John E. Hopcroft; Jeffrey D. Ullman (1967). "नॉनरेज़िंग स्टैक ऑटोमेटा". Journal of Computer and System Sciences. 1 (2): 166–186. doi:10.1016/s0022-0000(67)80013-8.

[Hopcroft.Ullman.1979-2] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 John E. Hopcroft and Jeffrey D. Ullman (1979). ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X.

[3] Holzer, Markus; Kutrib, Martin (2019). "Non-Recursive Trade-Offs Are "Almost Everywhere"". Computing with Foresight and Industry. 11558: 25–36. doi:10.1007/978-3-030-22996-2_3. This follows from the quoted [22, Proposition 7] and the stated observation that any deterministic pushdown automaton can be converted into an equivalent finite automaton^[clarify] of at most doubly-exponential size.

[5] Seymour Ginsburg, Sheila A. Greibach and Michael A. Harrison (1967). "स्टैक ऑटोमेटा और संकलन". J. ACM. 14 (1): 172–201. doi:10.1145/321371.321385.

[6] Seymour Ginsburg, Sheila A. Greibach and Michael A. Harrison (1967). "वन-वे स्टैक ऑटोमेटा". J. ACM. 14 (2): 389–418. doi:10.1145/321386.321403.

[ChandraKozen1981-7] Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "अदल-बदल". Journal of the ACM. 28 (1): 114–133. doi:10.1145/322234.322243. ISSN 0004-5411.

[LadnerLipton1984-8] Ladner, Richard E.; Lipton, Richard J.; Stockmeyer, Larry J. (1984). "वैकल्पिक पुशडाउन और स्टैक ऑटोमेटा". SIAM Journal on Computing. 13 (1): 135–155. doi:10.1137/0213010. ISSN 0097-5397.

[AizikowitzKaminski2011-9] Aizikowitz, Tamar; Kaminski, Michael (2011). "LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata". Computer Science – Theory and Applications. Lecture Notes in Computer Science. Vol. 6651. pp. 345–358. doi:10.1007/978-3-642-20712-9_27. ISBN 978-3-642-20711-2. ISSN 0302-9743.

[1]

[2]

[3]

[note 1]

[4]

[5]

[6]

[7]

[8]

@@ Line 1: / Line 1: @@
 {{short description|Type of automaton}}
 {{Automata theory}}
-गणना के सिद्धांत में, [[सैद्धांतिक कंप्यूटर विज्ञान]] की शाखा, पुशडाउन ऑटोमेटन (पीडीए) है
+गणना के सिद्धांत में, [[सैद्धांतिक कंप्यूटर विज्ञान]] की शाखा, पुशडाउन ऑटोमेटन (पीडीए) है एक प्रकार का [[ऑटोमेटा सिद्धांत]] जो एक [[स्टैक (डेटा संरचना)]] को नियोजित करता है।
-एक प्रकार का [[ऑटोमेटा सिद्धांत]] जो [[स्टैक (डेटा संरचना)]] को नियोजित करता है।
-मशीनों द्वारा क्या गणना की जा सकती है, इसके सिद्धांतों में पुशडाउन ऑटोमेटा का उपयोग किया जाता है। वे परिमित-राज्य मशीनों की तुलना में अधिक सक्षम हैं लेकिन [[ट्यूरिंग मशीन]]ों की तुलना में कम सक्षम हैं (#पीडीए और ट्यूरिंग मशीनें देखें)।
+मशीनों द्वारा क्या गणना की जा सकती है, इसके सिद्धांतों में पुशडाउन ऑटोमेटा का उपयोग किया जाता है। वे परिमित-स्थिति मशीनों की तुलना में अधिक सक्षम हैं परन्तु [[ट्यूरिंग मशीन|ट्यूरिंग मशीनों]] की तुलना में कम सक्षम हैं ( पीडीए और ट्यूरिंग मशीनें देखें)।
-[[नियतात्मक पुशडाउन ऑटोमेटा]] सभी नियतात्मक [[संदर्भ-मुक्त भाषा]]ओं को पहचान सकता है जबकि गैर-नियतात्मक सभी संदर्भ-मुक्त भाषाओं को पहचान सकता है, पूर्व का उपयोग अक्सर [[पार्सर]] डिज़ाइन में किया जाता है।
-पुशडाउन शब्द इस तथ्य को संदर्भित करता है कि स्टैक (अमूर्त डेटा प्रकार) को कैफेटेरिया में ट्रे डिस्पेंसर की तरह नीचे धकेलने के रूप में माना जा सकता है, क्योंकि ऑपरेशन कभी भी शीर्ष तत्व के अलावा अन्य तत्वों पर काम नहीं करते हैं। इसके विपरीत, स्टैक ऑटोमेटन, गहरे तत्वों तक पहुंच और संचालन की अनुमति देता है। स्टैक ऑटोमेटा पुशडाउन ऑटोमेटा की तुलना में भाषाओं के बड़े समूह को पहचान सकता है।<ref name="Hopcroft.Ullman.1967"/>एक [[नेस्टेड स्टैक ऑटोमेटन]] पूर्ण पहुंच की अनुमति देता है, और स्टैक्ड मानों को केवल एकल परिमित प्रतीकों के बजाय संपूर्ण उप-स्टैक होने की भी अनुमति देता है।
+[[नियतात्मक पुशडाउन ऑटोमेटा|डीटरमिनिस्ट पुशडाउन ऑटोमेटा]] सभी डीटरमिनिस्ट [[संदर्भ-मुक्त भाषा|डीटरमिनिस्ट कॉन्टेक्स्ट-फ्री लैंग्वेज]] को पहचान सकता है जबकि गैर-डीटरमिनिस्ट कॉन्टेक्स्ट-फ्री लैंग्वेज लैंग्वेज को पहचान सकता है, पूर्व का उपयोग प्रायः [[पार्सर]] डिज़ाइन में किया जाता है।
+पुशडाउन शब्द इस तथ्य को संदर्भित करता है कि स्टैक (अमूर्त डेटा प्रकार) को कैफेटेरिया में ट्रे डिस्पेंसर के जैसे नीचे पुशडाउन के रूप में माना जा सकता है, क्योंकि ऑपरेशन कभी भी शीर्ष अवयव के अतिरिक्त अन्य अवयवों पर कार्य नहीं करते हैं। इसके विपरीत, स्टैक ऑटोमेटन, गहन अवयवों तक एक्सेस और ऑपरेशन की अनुमति देता है। स्टैक ऑटोमेटा पुशडाउन ऑटोमेटा की तुलना में लैंग्वेज के बड़े समूह को पहचान सकता है।<ref name="Hopcroft.Ullman.1967" /> एक [[नेस्टेड स्टैक ऑटोमेटन]] पूर्ण एक्सेस की अनुमति देता है, और स्टैक्ड मानों को मात्र एकल परिमित प्रतीकों के अतिरिक्त संपूर्ण उप-स्टैक होने की भी अनुमति देता है।
 == अनौपचारिक विवरण ==
-[[Image:Pushdown-overview.svg|thumb|340px|पुशडाउन ऑटोमेटन का आरेख]]एक परिमित-राज्य मशीन केवल इनपुट सिग्नल और वर्तमान स्थिति को देखती है: इसके पास काम करने के लिए कोई स्टैक नहीं है। यह नया राज्य चुनता है, जो परिवर्तन का अनुसरण करने का परिणाम है। पुशडाउन ऑटोमेटन (पीडीए) परिमित राज्य मशीन से दो तरीकों से भिन्न होता है:
+[[Image:Pushdown-overview.svg|thumb|340px|पुशडाउन ऑटोमेटन का आरेख]]एक परिमित-स्थिति मशीन मात्र इनपुट सिग्नल और वर्तमान स्थिति को देखती है: इसके निकट कार्य करने के लिए कोई स्टैक नहीं है। यह नवीन स्थिति चुनता है, जो परिवर्तन का अनुसरण करने का परिणाम है। पुशडाउन ऑटोमेटन (पीडीए) परिमित स्थिति मशीन से दो विधियों से भिन्न होता है:
-# यह स्टैक के शीर्ष का उपयोग यह तय करने के लिए कर सकता है कि कौन सा संक्रमण लेना है।
+# यह स्टैक के शीर्ष का उपयोग यह निर्धारित करने के लिए कर सकता है कि कौन सा ट्रांजीशन लेना है।
-# यह संक्रमण निष्पादित करने के भाग के रूप में स्टैक में हेरफेर कर सकता है।
+# यह ट्रांजीशन निष्पादित करने के भाग के रूप में स्टैक में परिवर्तन कर सकता है।
-एक पुशडाउन ऑटोमेटन किसी दिए गए इनपुट स्ट्रिंग को बाएं से दाएं पढ़ता है। प्रत्येक चरण में, यह इनपुट प्रतीक, वर्तमान स्थिति और स्टैक के शीर्ष पर प्रतीक द्वारा तालिका को अनुक्रमित करके संक्रमण चुनता है।  ट्रांज़िशन निष्पादित करने के भाग के रूप में, पुशडाउन ऑटोमेटन स्टैक में हेरफेर भी कर सकता है। हेरफेर किसी विशेष प्रतीक को स्टैक के शीर्ष पर धकेलने या स्टैक के शीर्ष को पॉप करने के लिए हो सकता है। ऑटोमेटन वैकल्पिक रूप से स्टैक को अनदेखा कर सकता है, और इसे वैसे ही छोड़ सकता है।
+एक पुशडाउन ऑटोमेटन किसी दिए गए इनपुट स्ट्रिंग को बाएं से दाएं पढ़ता है। प्रत्येक चरण में, यह इनपुट प्रतीक, वर्तमान स्थिति और स्टैक के शीर्ष पर प्रतीक द्वारा तालिका को अनुक्रमित करके ट्रांजीशन चुनता है। ट्रांज़िशन निष्पादित करने के भाग के रूप में, पुशडाउन ऑटोमेटन स्टैक में परिवर्तन भी कर सकता है। परिवर्तन किसी विशेष प्रतीक को स्टैक के शीर्ष पर पुशडाउन या स्टैक के शीर्ष को पॉप करने के लिए हो सकता है। ऑटोमेटन वैकल्पिक रूप से स्टैक को अनदेखा कर सकता है, और इसे वैसे ही छोड़ सकता है। एक साथ रखें: इनपुट प्रतीक, वर्तमान स्थिति और स्टैक प्रतीक को देखते हुए, ऑटोमेटन किसी अन्य स्थिति में ट्रांजीशन का पालन कर सकता है, और वैकल्पिक रूप से स्टैक में परिवर्तन (पुश या पॉप) कर सकता है।
-एक साथ रखें: इनपुट प्रतीक, वर्तमान स्थिति और स्टैक प्रतीक को देखते हुए, ऑटोमेटन किसी अन्य राज्य में संक्रमण का पालन कर सकता है, और वैकल्पिक रूप से स्टैक में हेरफेर (पुश या पॉप) कर सकता है।
-यदि, हर स्थिति में, अधिकतम ऐसी संक्रमण क्रिया संभव है, तो ऑटोमेटन को [[नियतात्मक पुशडाउन ऑटोमेटन]] (DPDA) कहा जाता है। सामान्य तौर पर, यदि कई क्रियाएं संभव हैं, तो ऑटोमेटन को सामान्य, या गैर-नियतात्मक, पीडीए कहा जाता है। दी गई इनपुट स्ट्रिंग गैर-नियतात्मक पुशडाउन ऑटोमेटन को कई कॉन्फ़िगरेशन अनुक्रमों में से में चला सकती है; यदि उनमें से पूरी इनपुट स्ट्रिंग को पढ़ने के बाद स्वीकार्य कॉन्फ़िगरेशन की ओर ले जाता है, तो बाद वाले को ''ऑटोमेटन द्वारा स्वीकृत भाषा'' से संबंधित माना जाता है।
+यदि, प्रत्येक स्थिति में, अधिकतम ऐसी ट्रांजीशन क्रिया संभव है, तो ऑटोमेटन को [[नियतात्मक पुशडाउन ऑटोमेटन|डीटरमिनिस्ट पुशडाउन ऑटोमेटन]] (डीपीडीए) कहा जाता है। सामान्यतः, यदि कई क्रियाएं संभव हैं, तो ऑटोमेटन को सामान्य, या गैर-डीटरमिनिस्ट, पीडीए कहा जाता है। दी गई इनपुट स्ट्रिंग गैर-डीटरमिनिस्ट पुशडाउन ऑटोमेटन को कई कॉन्फ़िगरेशन अनुक्रमों में से एक में चला सकती है; यदि उनमें से पूर्ण इनपुट स्ट्रिंग को पढ़ने के बाद स्वीकार्य कॉन्फ़िगरेशन की ओर ले जाता है, तो बाद वाले को ''ऑटोमेटन द्वारा स्वीकृत'' लैंग्वेज से संबंधित माना जाता है।
-  संक्रमण संबंध
+  ट्रांजीशन संबंध
-*<math>q_{0} \in Q </math> प्रारंभ अवस्था है
+*<math>q_{0} \in Q </math> आरंभिक अवस्था है
 *<math>Z \in \Gamma</math> प्रारंभिक स्टैक प्रतीक है
-*<math>F \subseteq Q</math> स्वीकार करने वाले राज्यों का समूह है
+*<math>F \subseteq Q</math> स्वीकार करने वाले स्थितिों का समूह है
-तत्व <math>(p,a,A,q,\alpha) \in \delta</math> का संक्रमण है <math>M</math>. इसका अभिप्राय यह है कि <math>M</math>, राज्य में <math>p \in Q</math>, इनपुट पर <math>a \in \Sigma \cup \{\varepsilon\}</math> और साथ <math>A \in \Gamma</math> सबसे ऊपरी स्टैक प्रतीक के रूप में, पढ़ सकते हैं <math>a</math>, राज्य को बदलें <math>q</math>, जल्दी से आना <math>A</math>, इसे धक्का देकर प्रतिस्थापित करें <math>\alpha \in \Gamma^*</math>. <math>(\Sigma \cup \{\varepsilon\})</math> h> संक्रमण संबंध के घटक का उपयोग यह औपचारिक बनाने के लिए किया जाता है कि पीडीए या तो इनपुट से पत्र पढ़ सकता है, या इनपुट को अछूता छोड़कर आगे बढ़ सकता है।
+अवयव <math>(p,a,A,q,\alpha) \in \delta</math> का ट्रांजीशन है <math>M</math>. इसका अभिप्राय यह है कि <math>M</math>, स्थिति में <math>p \in Q</math>, इनपुट पर <math>a \in \Sigma \cup \{\varepsilon\}</math> और साथ <math>A \in \Gamma</math> सबसे ऊपरी स्टैक प्रतीक के रूप में, पढ़ सकते हैं <math>a</math>, स्थिति को बदलें <math>q</math>, जल्दी से आना <math>A</math>, इसे धक्का देकर प्रतिस्थापित करें <math>\alpha \in \Gamma^*</math>. <math>(\Sigma \cup \{\varepsilon\})</math> h> ट्रांजीशन संबंध के घटक का उपयोग यह औपचारिक बनाने के लिए किया जाता है कि पीडीए या तो इनपुट से पत्र पढ़ सकता है, या इनपुट को अछूता छोड़कर आगे बढ़ सकता है।
-अनेक ग्रंथों में<ref name="Hopcroft.Ullman.1979"/>{{rp|110}} संक्रमण संबंध को (समतुल्य) औपचारिकता द्वारा प्रतिस्थापित किया जाता है, जहां
+अनेक ग्रंथों में<ref name="Hopcroft.Ullman.1979"/>{{rp|110}} ट्रांजीशन संबंध को (समतुल्य) औपचारिकता द्वारा प्रतिस्थापित किया जाता है, जहां
-* <math>\delta</math> संक्रमण फ़ंक्शन, मैपिंग है <math>Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma</math> के परिमित उपसमुच्चय में <math>Q \times \Gamma^*</math>
+* <math>\delta</math> ट्रांजीशन फ़ंक्शन, मैपिंग है <math>Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma</math> के परिमित उपसमुच्चय में <math>Q \times \Gamma^*</math>
-यहाँ <math>\delta(p, a, A)</math> राज्य में सभी संभावित कार्रवाइयां शामिल हैं <math>p</math> साथ <math>A</math> पढ़ते समय, स्टैक पर <math>a</math> इनपुट पर. उदाहरण के लिए कोई लिखता है <math>\delta(p, a, A) = \{(q, BA)\}</math> बिल्कुल कब <math>(q, BA) \in \{(q, BA)\}, (q, BA) \in \delta(p, a, A),</math> क्योंकि <math>((p, a, A), \{(q, BA)\}) \in \delta</math>. ध्यान दें कि इस परिभाषा में परिमित आवश्यक है।
+यहाँ <math>\delta(p, a, A)</math> स्थिति में सभी संभावित कार्रवाइयां शामिल हैं <math>p</math> साथ <math>A</math> पढ़ते समय, स्टैक पर <math>a</math> इनपुट पर. उदाहरण के लिए कोई लिखता है <math>\delta(p, a, A) = \{(q, BA)\}</math> बिल्कुल कब <math>(q, BA) \in \{(q, BA)\}, (q, BA) \in \delta(p, a, A),</math> क्योंकि <math>((p, a, A), \{(q, BA)\}) \in \delta</math>. ध्यान दें कि इस परिलैंग्वेज में परिमित आवश्यक है।
 'गणना'
-[[Image:Pushdown-step.svg|thumb|200px|पुशडाउन ऑटोमेटन का चरण]]पुशडाउन ऑटोमेटन के शब्दार्थ को औपचारिक बनाने के लिए वर्तमान स्थिति का विवरण प्रस्तुत किया गया है। कोई भी 3-टुपल <math>(p,w,\beta) \in Q \times \Sigma^* \times \Gamma^*</math> का तात्कालिक विवरण (आईडी) कहा जाता है <math>M</math>, जिसमें वर्तमान स्थिति, इनपुट टेप का वह हिस्सा जो पढ़ा नहीं गया है, और स्टैक की सामग्री (सबसे ऊपर का प्रतीक पहले लिखा गया है) शामिल है। संक्रमण संबंध <math>\delta</math> चरण-संबंध को परिभाषित करता है <math>\vdash_{M}</math> का <math>M</math> तात्कालिक विवरण पर. निर्देश हेतु <math>(p,a,A,q,\alpha) \in \delta</math> वहाँ कदम मौजूद है <math>(p,ax,A\gamma) \vdash_{M} (q,x,\alpha\gamma)</math>, हरएक के लिए <math>x\in\Sigma^*</math> और हर <math>\gamma\in \Gamma^*</math>.
+[[Image:Pushdown-step.svg|thumb|200px|पुशडाउन ऑटोमेटन का चरण]]पुशडाउन ऑटोमेटन के शब्दार्थ को औपचारिक बनाने के लिए वर्तमान स्थिति का विवरण प्रस्तुत किया गया है। कोई भी 3-टुपल <math>(p,w,\beta) \in Q \times \Sigma^* \times \Gamma^*</math> का तात्कालिक विवरण (आईडी) कहा जाता है <math>M</math>, जिसमें वर्तमान स्थिति, इनपुट टेप का वह हिस्सा जो पढ़ा नहीं गया है, और स्टैक की सामग्री (सबसे ऊपर का प्रतीक पहले लिखा गया है) शामिल है। ट्रांजीशन संबंध <math>\delta</math> चरण-संबंध को परिभाषित करता है <math>\vdash_{M}</math> का <math>M</math> तात्कालिक विवरण पर. निर्देश हेतु <math>(p,a,A,q,\alpha) \in \delta</math> वहाँ कदम मौजूद है <math>(p,ax,A\gamma) \vdash_{M} (q,x,\alpha\gamma)</math>, हरएक के लिए <math>x\in\Sigma^*</math> और प्रत्येक <math>\gamma\in \Gamma^*</math>.
-सामान्य तौर पर पुशडाउन ऑटोमेटा किसी दिए गए तात्कालिक विवरण में गैर-नियतात्मक अर्थ होता है <math>(p,w,\beta)</math> कई संभावित कदम हो सकते हैं. गणना में इनमें से कोई भी चरण चुना जा सकता है।
+सामान्यतः पुशडाउन ऑटोमेटा किसी दिए गए तात्कालिक विवरण में गैर-डीटरमिनिस्ट अर्थ होता है <math>(p,w,\beta)</math> कई संभावित कदम हो सकते हैं. गणना में इनमें से कोई भी चरण चुना जा सकता है।
-उपरोक्त परिभाषा के साथ प्रत्येक चरण में हमेशा एकल प्रतीक (स्टैक के शीर्ष) को पॉप किया जाता है, इसे आवश्यकतानुसार कई प्रतीकों से बदल दिया जाता है। परिणामस्वरूप, स्टैक खाली होने पर कोई चरण परिभाषित नहीं होता है।
+उपरोक्त परिलैंग्वेज के साथ प्रत्येक चरण में हमेशा एकल प्रतीक (स्टैक के शीर्ष) को पॉप किया जाता है, इसे आवश्यकतानुसार कई प्रतीकों से बदल दिया जाता है। परिणामस्वरूप, स्टैक खाली होने पर कोई चरण परिभाषित नहीं होता है।
 पुशडाउन ऑटोमेटन की गणना चरणों का क्रम है। गणना प्रारम्भिक अवस्था में प्रारम्भ होती है <math>q_{0}</math> प्रारंभिक स्टैक प्रतीक के साथ <math>Z</math> ढेर पर, और स्ट्रिंग <math>w</math> इनपुट टेप पर, इस प्रकार प्रारंभिक विवरण के साथ <math>(q_{0},w,Z)</math>.
@@ Line 45: / Line 44: @@
 # <math>N(M) = \{ w\in\Sigma^* | (q_{0},w,Z) \vdash_M^* (q,\varepsilon,\varepsilon)</math> साथ <math>q \in Q \}</math> (खाली ढेर)
-यहाँ <math>\vdash_M^*</math> चरण संबंध के [[ प्रतिवर्ती समापन ]] और [[ सकर्मक समापन ]] का प्रतिनिधित्व करता है <math>\vdash_M</math> मतलब लगातार चरणों की कोई भी संख्या (शून्य, या अधिक)।
+यहाँ <math>\vdash_M^*</math> चरण संबंध के [[ प्रतिवर्ती समापन |प्रतिवर्ती समापन]] और [[ सकर्मक समापन |सकर्मक समापन]] का प्रतिनिधित्व करता है <math>\vdash_M</math> मतलब लगातार चरणों की कोई भी संख्या (शून्य, या अधिक)।
-प्रत्येक एकल पुशडाउन ऑटोमेटन के लिए इन दोनों भाषाओं का कोई संबंध नहीं होना चाहिए: वे समान हो सकते हैं लेकिन आमतौर पर ऐसा नहीं होता है। ऑटोमेटन के विनिर्देश में स्वीकृति का इच्छित तरीका भी शामिल होना चाहिए। सभी पुशडाउन ऑटोमेटा पर आधारित दोनों स्वीकृति शर्तें भाषाओं के ही परिवार को परिभाषित करती हैं।
+प्रत्येक एकल पुशडाउन ऑटोमेटन के लिए इन दोनों लैंग्वेज का कोई संबंध नहीं होना चाहिए: वे समान हो सकते हैं परन्तु आमतौर पर ऐसा नहीं होता है। ऑटोमेटन के विनिर्देश में स्वीकृति का इच्छित तरीका भी शामिल होना चाहिए। सभी पुशडाउन ऑटोमेटा पर आधारित दोनों स्वीकृति शर्तें लैंग्वेज के ही परिवार को परिभाषित करती हैं।
 प्रमेय. प्रत्येक पुशडाउन ऑटोमेटन के लिए <math>M</math> कोई पुशडाउन ऑटोमेटन का निर्माण कर सकता है <math>M'</math> ऐसा है कि <math>L(M)=N(M')</math>, और इसके विपरीत, प्रत्येक पुशडाउन ऑटोमेटन के लिए <math>M</math> कोई पुशडाउन ऑटोमेटन का निर्माण कर सकता है <math>M'</math> ऐसा है कि <math>N(M)=L(M')</math>
 == उदाहरण ==
-निम्नलिखित पीडीए का औपचारिक विवरण है जो भाषा को पहचानता है <math>\{0^n1^n \mid n \ge 0 \}</math> अंतिम स्थिति के अनुसार:
+निम्नलिखित पीडीए का औपचारिक विवरण है जो लैंग्वेज को पहचानता है <math>\{0^n1^n \mid n \ge 0 \}</math> अंतिम स्थिति के अनुसार:
 [[Image:Pda-example.svg|thumb|200px|के लिए पीडीए <math>\{0^n1^n \mid n \ge 0\}</math><br/>(अंतिम स्थिति के अनुसार)]]
@@ Line 63: / Line 62: @@
 *स्टार्ट स्टैक प्रतीक: {{mvar|Z}}
 * स्वीकार करने की स्थिति: <math>F = \{r\}</math>
-संक्रमण संबंध <math>\delta</math> निम्नलिखित छह निर्देश शामिल हैं:
+ट्रांजीशन संबंध <math>\delta</math> निम्नलिखित छह निर्देश शामिल हैं:
 :<math>(p,0,Z,p,AZ)</math>,
@@ Line 72: / Line 71: @@
 :<math>(q,\epsilon,Z,r,Z)</math>.
-शब्दों में, पहले दो निर्देश कहते हैं कि स्थिति में {{mvar|p}} किसी भी समय प्रतीक {{val|0}} पढ़ा जाता है, {{mvar|A}} को स्टैक पर धकेल दिया जाता है। धक्का देने वाला प्रतीक {{mvar|A}} दूसरे के ऊपर {{mvar|A}} को शीर्ष के स्थान पर औपचारिक रूप दिया गया है {{mvar|A}} द्वारा {{mvar|AA}} (और इसी तरह प्रतीक को आगे बढ़ाने के लिए {{mvar|A}}ए के शीर्ष पर {{mvar|Z}}).
+शब्दों में, पहले दो निर्देश कहते हैं कि स्थिति में {{mvar|p}} किसी भी समय प्रतीक {{val|0}} पढ़ा जाता है, {{mvar|A}} को स्टैक पर पुशडाउन किया जाता है। धक्का देने वाला प्रतीक {{mvar|A}} दूसरे के ऊपर {{mvar|A}} को शीर्ष के स्थान पर औपचारिक रूप दिया गया है {{mvar|A}} द्वारा {{mvar|AA}} (और इसी प्रकार प्रतीक को आगे बढ़ाने के लिए {{mvar|A}}ए के शीर्ष पर {{mvar|Z}}).
-तीसरे और चौथे निर्देश कहते हैं कि, किसी भी क्षण ऑटोमेटन राज्य से हट सकता है {{mvar|p}} कहना {{mvar|q}}.
+तीसरे और चौथे निर्देश कहते हैं कि, किसी भी क्षण ऑटोमेटन स्थिति से हट सकता है {{mvar|p}} कहना {{mvar|q}}.
-पांचवां निर्देश कहता है कि राज्य में {{mvar|q}}, प्रत्येक प्रतीक के लिए {{val|1}} पढ़ें, {{mvar|A}} पॉप हो गया है.
+पांचवां निर्देश कहता है कि स्थिति में {{mvar|q}}, प्रत्येक प्रतीक के लिए {{val|1}} पढ़ें, {{mvar|A}} पॉप हो गया है.
-अंत में, छठा निर्देश कहता है कि मशीन राज्य से आगे बढ़ सकती है {{mvar|q}} राज्य को स्वीकार करने के लिए {{mvar|r}} केवल तभी जब स्टैक में एकल शामिल हो {{mvar|Z}}.
+अंत में, छठा निर्देश कहता है कि मशीन स्थिति से आगे बढ़ सकती है {{mvar|q}} स्थिति को स्वीकार करने के लिए {{mvar|r}} मात्र तभी जब स्टैक में एकल शामिल हो {{mvar|Z}}.
-ऐसा लगता है कि पीडीए के लिए आम तौर पर इस्तेमाल किया जाने वाला कोई प्रतिनिधित्व नहीं है। यहां हमने निर्देश दर्शाया है <math>(p,a,A,q,\alpha)</math> राज्य से बढ़त से {{mvar|p}} कहना {{mvar|q}} द्वारा लेबल किया गया  <math>a; A/\alpha</math> (पढ़ना {{mvar|a}}; बदलना {{mvar|A}} द्वारा <math>\alpha</math>).
+ऐसा लगता है कि पीडीए के लिए आम तौर पर इस्तेमाल किया जाने वाला कोई प्रतिनिधित्व नहीं है। यहां हमने निर्देश दर्शाया है <math>(p,a,A,q,\alpha)</math> स्थिति से बढ़त से {{mvar|p}} कहना {{mvar|q}} द्वारा लेबल किया गया <math>a; A/\alpha</math> (पढ़ना {{mvar|a}}; बदलना {{mvar|A}} द्वारा <math>\alpha</math>).
 === गणना प्रक्रिया को समझना ===
@@ Line 97: / Line 96: @@
 }}
-==पीडीए और संदर्भ-मुक्त भाषाएँ==
+==पीडीए और संदर्भ-मुक्त लैंग्वेज==
-प्रत्येक [[संदर्भ-मुक्त व्याकरण]] को समतुल्य गैर-नियतात्मक पुशडाउन ऑटोमेटन में परिवर्तित किया जा सकता है। व्याकरण की व्युत्पत्ति प्रक्रिया को सबसे बाएं तरीके से अनुकरण किया जाता है। जहां व्याकरण नॉनटर्मिनल को फिर से लिखता है, पीडीए अपने स्टैक से सबसे ऊपरी नॉनटर्मिनल लेता है और इसे व्याकरणिक नियम (विस्तार) के दाहिने हाथ के हिस्से से बदल देता है। जहां व्याकरण टर्मिनल प्रतीक उत्पन्न करता है, पीडीए इनपुट से प्रतीक पढ़ता है जब यह स्टैक (मैच) पर सबसे ऊपरी प्रतीक होता है। अर्थ में पीडीए के स्टैक में व्याकरण का असंसाधित डेटा होता है, जो व्युत्पत्ति वृक्ष के प्री-ऑर्डर ट्रैवर्सल के अनुरूप होता है।
+प्रत्येक [[संदर्भ-मुक्त व्याकरण]] को समतुल्य गैर-डीटरमिनिस्ट पुशडाउन ऑटोमेटन में परिवर्तित किया जा सकता है। व्याकरण की व्युत्पत्ति प्रक्रिया को सबसे बाएं तरीके से अनुकरण किया जाता है। जहां व्याकरण नॉनटर्मिनल को फिर से लिखता है, पीडीए अपने स्टैक से सबसे ऊपरी नॉनटर्मिनल लेता है और इसे व्याकरणिक नियम (विस्तार) के दाहिने हाथ के हिस्से से बदल देता है। जहां व्याकरण टर्मिनल प्रतीक उत्पन्न करता है, पीडीए इनपुट से प्रतीक पढ़ता है जब यह स्टैक (मैच) पर सबसे ऊपरी प्रतीक होता है। अर्थ में पीडीए के स्टैक में व्याकरण का असंसाधित डेटा होता है, जो व्युत्पत्ति वृक्ष के प्री-ऑर्डर ट्रैवर्सल के अनुरूप होता है।
-तकनीकी रूप से, संदर्भ-मुक्त व्याकरण को देखते हुए, पीडीए की ही स्थिति है, 1, और इसका संक्रमण संबंध इस प्रकार बनाया गया है।
+तकनीकी रूप से, संदर्भ-मुक्त व्याकरण को देखते हुए, पीडीए की ही स्थिति है, 1, और इसका ट्रांजीशन संबंध इस प्रकार बनाया गया है।
 # <math>(1,\varepsilon,A,1,\alpha)</math> प्रत्येक नियम के लिए <math>A\to\alpha</math> (बढ़ाना)
@@ Line 108: / Line 107: @@
 पीडीए खाली स्टैक द्वारा स्वीकार करता है। इसका प्रारंभिक स्टैक प्रतीक व्याकरण का प्रारंभ प्रतीक है।{{citation needed|date=December 2016}}
-ग्रीबैक सामान्य रूप में संदर्भ-मुक्त व्याकरण के लिए, प्रत्येक व्याकरण नियम ए → एγ के लिए (1,γ) ∈ δ(1,a,A) को परिभाषित करने से समतुल्य गैर-नियतात्मक पुशडाउन ऑटोमेटन भी प्राप्त होता है।<ref name="Hopcroft.Ullman.1979">{{cite book | isbn=0-201-02988-X | author=John E. Hopcroft and Jeffrey D. Ullman | title=ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय| location=Reading/MA | publisher=Addison-Wesley | year=1979 | url-access=registration | url=https://archive.org/details/introductiontoau00hopc }}</ref>{{rp|115}}
+ग्रीबैक सामान्य रूप में संदर्भ-मुक्त व्याकरण के लिए, प्रत्येक व्याकरण नियम ए → एγ के लिए (1,γ) ∈ δ(1,a,A) को परिभाषित करने से समतुल्य गैर-डीटरमिनिस्ट पुशडाउन ऑटोमेटन भी प्राप्त होता है।<ref name="Hopcroft.Ullman.1979">{{cite book | isbn=0-201-02988-X | author=John E. Hopcroft and Jeffrey D. Ullman | title=ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय| location=Reading/MA | publisher=Addison-Wesley | year=1979 | url-access=registration | url=https://archive.org/details/introductiontoau00hopc }}</ref>{{rp|115}}
-किसी दिए गए पीडीए के लिए व्याकरण ढूंढना इतना आसान नहीं है। चाल पीडीए के दो राज्यों को व्याकरण के गैर-टर्मिनलों में कोड करने की है।
+किसी दिए गए पीडीए के लिए व्याकरण ढूंढना इतना आसान नहीं है। चाल पीडीए के दो स्थितिों को व्याकरण के गैर-टर्मिनलों में कोड करने की है।
 प्रमेय. प्रत्येक पुशडाउन ऑटोमेटन के लिए <math>M</math> कोई संदर्भ-मुक्त व्याकरण का निर्माण कर सकता है <math>G</math> ऐसा है कि {{nobr|<math>N(M)=L(G)</math>.}}<ref name="Hopcroft.Ullman.1979"/>{{rp|116}}
-नियतात्मक पुशडाउन ऑटोमेटन (DPDA) द्वारा स्वीकृत स्ट्रिंग्स की भाषा को नियतात्मक संदर्भ-मुक्त भाषा कहा जाता है। सभी संदर्भ-मुक्त भाषाएँ नियतिवादी नहीं हैं।परिणामस्वरूप, डीपीडीए पीडीए का सख्ती से कमजोर संस्करण है। यहां तक कि [[नियमित भाषा]]ओं के लिए भी, आकार विस्फोट की समस्या है: किसी भी सामान्य पुनरावर्ती फ़ंक्शन के लिए <math>f</math> और मनमाने ढंग से बड़े पूर्णांकों के लिए <math>n</math>, आकार का पीडीए है <math>n</math> नियमित भाषा का वर्णन करना जिसकी सबसे छोटी DPDA के पास कम से कम है <math>f(n)</math> राज्य.<ref>{{cite journal |last1=Holzer |first1=Markus |last2=Kutrib |first2=Martin |title=Non-Recursive Trade-Offs Are “Almost Everywhere” |journal=Computing with Foresight and Industry |date=2019 |volume=11558 |pages=25–36 |doi=10.1007/978-3-030-22996-2_3}} This follows from the quoted [22, Proposition 7] and the stated observation that {{clarify span|any deterministic pushdown automaton can be converted into an equivalent finite automaton|reason=A finite automaton cannot be equivalent to a pushdown automaton, unless the latter doesn't actually use its stack.|date=June 2022}} of at most doubly-exponential size.</ref> कई गैर-नियमित पीडीए के लिए, किसी भी समकक्ष डीपीडीए को असीमित संख्या में राज्यों की आवश्यकता होगी।
+डीटरमिनिस्ट पुशडाउन ऑटोमेटन (डीपीडीए) द्वारा स्वीकृत स्ट्रिंग्स की लैंग्वेज को डीटरमिनिस्ट संदर्भ-मुक्त लैंग्वेज कहा जाता है। सभी संदर्भ-मुक्त लैंग्वेज नियतिवादी नहीं हैं।परिणामस्वरूप, डीपीडीए पीडीए का सख्ती से कमजोर संस्करण है। यहां तक कि [[नियमित भाषा|नियमित]] लैंग्वेज के लिए भी, आकार विस्फोट की समस्या है: किसी भी सामान्य पुनरावर्ती फ़ंक्शन के लिए <math>f</math> और मनमाने ढंग से बड़े पूर्णांकों के लिए <math>n</math>, आकार का पीडीए है <math>n</math> नियमित लैंग्वेज का वर्णन करना जिसकी सबसे छोटी डीपीडीए के निकट कम से कम है <math>f(n)</math> स्थिति.<ref>{{cite journal |last1=Holzer |first1=Markus |last2=Kutrib |first2=Martin |title=Non-Recursive Trade-Offs Are “Almost Everywhere” |journal=Computing with Foresight and Industry |date=2019 |volume=11558 |pages=25–36 |doi=10.1007/978-3-030-22996-2_3}} This follows from the quoted [22, Proposition 7] and the stated observation that {{clarify span|any deterministic pushdown automaton can be converted into an equivalent finite automaton|reason=A finite automaton cannot be equivalent to a pushdown automaton, unless the latter doesn't actually use its stack.|date=June 2022}} of at most doubly-exponential size.</ref> कई गैर-नियमित पीडीए के लिए, किसी भी समकक्ष डीपीडीए को असीमित संख्या में स्थितिों की आवश्यकता होगी।
-दो स्टैक तक पहुंच वाला सीमित ऑटोमेटन अधिक शक्तिशाली उपकरण है, जो ट्यूरिंग मशीन की शक्ति के बराबर है।<ref name="Hopcroft.Ullman.1979"/>{{rp|171}} [[रैखिक परिबद्ध ऑटोमेटन]] उपकरण है जो पुशडाउन ऑटोमेटन से अधिक शक्तिशाली है लेकिन ट्यूरिंग मशीन से कम शक्तिशाली है।{{#tag:ref|Linear bounded automata are acceptors for the class of context-sensitive languages,<ref name="Hopcroft.Ullman.1979"/>{{rp|225}} which is a proper superclass of the context-free languages, and a proper subclass of Turing-recognizable (i.e. [[recursively enumerable]]) languages.<ref name="Hopcroft.Ullman.1979"/>{{rp|228}}|group=note}}
+दो स्टैक तक एक्सेस वाला सीमित ऑटोमेटन अधिक शक्तिशाली उपकरण है, जो ट्यूरिंग मशीन की शक्ति के बराबर है।<ref name="Hopcroft.Ullman.1979"/>{{rp|171}} [[रैखिक परिबद्ध ऑटोमेटन]] उपकरण है जो पुशडाउन ऑटोमेटन से अधिक शक्तिशाली है परन्तु ट्यूरिंग मशीन से कम शक्तिशाली है।{{#tag:ref|Linear bounded automata are acceptors for the class of context-sensitive languages,<ref name="Hopcroft.Ullman.1979"/>{{rp|225}} which is a proper superclass of the context-free languages, and a proper subclass of Turing-recognizable (i.e. [[recursively enumerable]]) languages.<ref name="Hopcroft.Ullman.1979"/>{{rp|228}}|group=note}}
 ==पीडीए और ट्यूरिंग मशीनें==
-एक पुशडाउन ऑटोमेटन कम्प्यूटेशनल रूप से दो टेपों के साथ 'प्रतिबंधित' ट्यूरिंग मशीन (टीएम) के बराबर है जो निम्नलिखित तरीके से प्रतिबंधित है- पहले टेप पर, टीएम केवल इनपुट पढ़ सकता है और बाएं से दाएं जा सकता है (यह परिवर्तन नहीं कर सकता)। दूसरे टेप पर, यह केवल डेटा को 'पुश' और 'पॉप' कर सकता है। या समकक्ष, यह पढ़ सकता है, लिख सकता है और बाएँ और दाएँ घूम सकता है, इस प्रतिबंध के साथ कि यह प्रत्येक चरण में केवल ही कार्य कर सकता है या तो स्ट्रिंग (पॉप) में सबसे बाएँ वर्ण को हटाना है या स्ट्रिंग (पुश) में सबसे बाएँ वर्ण के बाएँ अतिरिक्त वर्ण जोड़ना है।
+एक पुशडाउन ऑटोमेटन कम्प्यूटेशनल रूप से दो टेपों के साथ 'प्रतिबंधित' ट्यूरिंग मशीन (टीएम) के बराबर है जो निम्नलिखित तरीके से प्रतिबंधित है- पहले टेप पर, टीएम मात्र इनपुट पढ़ सकता है और बाएं से दाएं जा सकता है (यह परिवर्तन नहीं कर सकता)। दूसरे टेप पर, यह मात्र डेटा को 'पुश' और 'पॉप' कर सकता है। या समकक्ष, यह पढ़ सकता है, लिख सकता है और बाएँ और दाएँ घूम सकता है, इस प्रतिबंध के साथ कि यह प्रत्येक चरण में मात्र ही कार्य कर सकता है या तो स्ट्रिंग (पॉप) में सबसे बाएँ वर्ण को हटाना है या स्ट्रिंग (पुश) में सबसे बाएँ वर्ण के बाएँ अतिरिक्त वर्ण जोड़ना है।
-पीडीए टीएम से कमजोर है, इसे इस तथ्य से समझा जा सकता है कि प्रक्रिया 'पॉप' कुछ डेटा को हटा देती है। पीडीए को टीएम जितना मजबूत बनाने के लिए, हमें 'पॉप' के माध्यम से खोए गए डेटा को कहीं सहेजना होगा। हम दूसरा स्टैक शुरू करके इसे हासिल कर सकते हैं। अंतिम पैराग्राफ के पीडीए के टीएम मॉडल में, यह 3 टेप वाले टीएम के बराबर है, जहां पहला टेप केवल-पढ़ने के लिए इनपुट टेप है, और दूसरा और तीसरा टेप 'पुश और पॉप' (स्टैक) टेप हैं। ऐसे पीडीए के लिए किसी दिए गए टीएम का अनुकरण करने के लिए, हम दोनों स्टैक को खाली रखते हुए, पहले टेप में पीडीए का इनपुट देते हैं। इसके बाद यह इनपुट टेप से सभी इनपुट को पहले स्टैक तक धकेलता है। जब संपूर्ण इनपुट को पहले स्टैक में स्थानांतरित कर दिया जाता है, तो अब हम सामान्य टीएम की तरह आगे बढ़ते हैं, जहां टेप पर दाईं ओर जाना पहले स्टैक से प्रतीक को पॉप करने और दूसरे स्टैक में (संभवतः अपडेट किए गए) प्रतीक को धकेलने के समान है, और बाईं ओर जाने से दूसरे स्टैक से प्रतीक को पॉप करने और (संभवतः अपडेट किए गए) प्रतीक को पहले स्टैक में धकेलने के समान होता है। इसलिए हमारे पास 2 स्टैक वाला पीडीए है जो किसी भी टीएम का अनुकरण कर सकता है।
+पीडीए टीएम से कमजोर है, इसे इस तथ्य से समझा जा सकता है कि प्रक्रिया 'पॉप' कुछ डेटा को हटा देती है। पीडीए को टीएम जितना मजबूत बनाने के लिए, हमें 'पॉप' के माध्यम से खोए गए डेटा को कहीं सहेजना होगा। हम दूसरा स्टैक शुरू करके इसे हासिल कर सकते हैं। अंतिम पैराग्राफ के पीडीए के टीएम मॉडल में, यह 3 टेप वाले टीएम के बराबर है, जहां पहला टेप मात्र-पढ़ने के लिए इनपुट टेप है, और दूसरा और तीसरा टेप 'पुश और पॉप' (स्टैक) टेप हैं। ऐसे पीडीए के लिए किसी दिए गए टीएम का अनुकरण करने के लिए, हम दोनों स्टैक को खाली रखते हुए, पहले टेप में पीडीए का इनपुट देते हैं। इसके बाद यह इनपुट टेप से सभी इनपुट को पहले स्टैक तक पुशडाउन करता है। जब संपूर्ण इनपुट को पहले स्टैक में स्थानांतरित कर दिया जाता है, तो अब हम सामान्य टीएम के जैसे आगे बढ़ते हैं, जहां टेप पर दाईं ओर जाना पहले स्टैक से प्रतीक को पॉप करने और दूसरे स्टैक में (संभवतः अपडेट किए गए) प्रतीक को पुशडाउन के समान है, और बाईं ओर जाने से दूसरे स्टैक से प्रतीक को पॉप करने और (संभवतः अपडेट किए गए) प्रतीक को पहले स्टैक में पुशडाउन के समान होता है। इसलिए हमारे निकट 2 स्टैक वाला पीडीए है जो किसी भी टीएम का अनुकरण कर सकता है।
 ==सामान्यीकृत पुशडाउन ऑटोमेटन (जीपीडीए)==
-जीपीडीए पीडीए है जो स्टैक पर कुछ ज्ञात लंबाई की पूरी स्ट्रिंग लिखता है या चरण में स्टैक से पूरी स्ट्रिंग को हटा देता है।
+जीपीडीए पीडीए है जो स्टैक पर कुछ ज्ञात लंबाई की पूर्ण स्ट्रिंग लिखता है या चरण में स्टैक से पूर्ण स्ट्रिंग को हटा देता है।
 GPDA को औपचारिक रूप से 6-टुपल के रूप में परिभाषित किया गया है:
 :<math>M=(Q,\  \Sigma,\  \Gamma,\  \delta, \ q_{0}, \ F)</math>
-कहाँ <math>Q, \Sigma\,, \Gamma\,, q_0</math>, और {{tmath|F}} को पीडीए की तरह ही परिभाषित किया गया है।
+कहाँ <math>Q, \Sigma\,, \Gamma\,, q_0</math>, और {{tmath|F}} को पीडीए के जैसे ही परिभाषित किया गया है।
 :<math>\,\delta</math>: <math>Q \times  \Sigma_{\epsilon}  \times \Gamma^{*} \longrightarrow P( Q \times \Gamma^{*} )</math>
-संक्रमण फलन है.
+ट्रांजीशन फलन है.
-जीपीडीए के लिए गणना नियम पीडीए के समान हैं, सिवाय इसके कि <math>a_{i+1}</math>'रेत <math>b_{i+1}</math>अब प्रतीकों के बजाय तार हैं।
+जीपीडीए के लिए गणना नियम पीडीए के समान हैं, सिवाय इसके कि <math>a_{i+1}</math>'रेत <math>b_{i+1}</math>अब प्रतीकों के अतिरिक्त तार हैं।
-जीपीडीए और पीडीए इस मायने में समतुल्य हैं कि यदि कोई भाषा पीडीए द्वारा मान्यता प्राप्त है, तो इसे जीपीडीए द्वारा भी मान्यता प्राप्त है और इसके विपरीत भी।
+जीपीडीए और पीडीए इस मायने में समतुल्य हैं कि यदि कोई लैंग्वेज पीडीए द्वारा मान्यता प्राप्त है, तो इसे जीपीडीए द्वारा भी मान्यता प्राप्त है और इसके विपरीत भी।
 निम्नलिखित सिमुलेशन का उपयोग करके जीपीडीए और पीडीए की तुल्यता के लिए विश्लेषणात्मक प्रमाण तैयार किया जा सकता है:
@@ Line 164: / Line 163: @@
 \end{array}</math>
 ==स्टैक ऑटोमेटन==
-पुशडाउन ऑटोमेटा के सामान्यीकरण के रूप में, गिंसबर्ग, ग्रीबैक और हैरिसन (1967) ने स्टैक ऑटोमेटा की जांच की, जो अतिरिक्त रूप से इनपुट स्ट्रिंग में बाएं या दाएं कदम रख सकता है (बाहर फिसलने से रोकने के लिए विशेष एंडमार्कर प्रतीकों से घिरा हुआ), और ऊपर या नीचे कदम रख सकता है केवल-पढ़ने योग्य मोड में स्टैक करें।<ref>{{cite journal| author=Seymour Ginsburg, Sheila A. Greibach and Michael A. Harrison| title=स्टैक ऑटोमेटा और संकलन| journal=J. ACM| year=1967| volume=14| number=1| pages=172–201| doi=10.1145/321371.321385| doi-access=free}}</ref><ref>{{cite journal| author=Seymour Ginsburg, Sheila A. Greibach and Michael A. Harrison| title=वन-वे स्टैक ऑटोमेटा| journal=J. ACM| year=1967| volume=14| number=2| pages=389–418| doi=10.1145/321386.321403}}</ref> स्टैक ऑटोमेटन को नॉनरेज़िंग कहा जाता है यदि यह स्टैक से कभी नहीं निकलता है। नॉनडेटर्मिनिस्टिक, नॉनरेज़िंग स्टैक ऑटोमेटा द्वारा स्वीकृत भाषाओं का वर्ग [[NSPACE]](n) है<sup>2</sup>), जो संदर्भ-संवेदनशील भाषाओं#कम्प्यूटेशनल गुणों|संदर्भ-संवेदनशील भाषाओं का सुपरसेट है।<ref name="Hopcroft.Ullman.1967">{{cite journal|author1=John E. Hopcroft |author2=Jeffrey D. Ullman | title=नॉनरेज़िंग स्टैक ऑटोमेटा| journal=Journal of Computer and System Sciences| year=1967| volume=1| number=2| pages=166–186| doi=10.1016/s0022-0000(67)80013-8| doi-access=free}}</ref> नियतात्मक, नॉनरेज़िंग स्टैक ऑटोमेटा द्वारा स्वीकृत भाषाओं का वर्ग [[DSPACE]](n⋅log(n)) है।<ref name="Hopcroft.Ullman.1967"/>
+पुशडाउन ऑटोमेटा के सामान्यीकरण के रूप में, गिंसबर्ग, ग्रीबैक और हैरिसन (1967) ने स्टैक ऑटोमेटा की जांच की, जो अतिरिक्त रूप से इनपुट स्ट्रिंग में बाएं या दाएं कदम रख सकता है (बाहर फिसलने से रोकने के लिए विशेष एंडमार्कर प्रतीकों से घिरा हुआ), और ऊपर या नीचे कदम रख सकता है मात्र-पढ़ने योग्य मोड में स्टैक करें।<ref>{{cite journal| author=Seymour Ginsburg, Sheila A. Greibach and Michael A. Harrison| title=स्टैक ऑटोमेटा और संकलन| journal=J. ACM| year=1967| volume=14| number=1| pages=172–201| doi=10.1145/321371.321385| doi-access=free}}</ref><ref>{{cite journal| author=Seymour Ginsburg, Sheila A. Greibach and Michael A. Harrison| title=वन-वे स्टैक ऑटोमेटा| journal=J. ACM| year=1967| volume=14| number=2| pages=389–418| doi=10.1145/321386.321403}}</ref> स्टैक ऑटोमेटन को नॉनरेज़िंग कहा जाता है यदि यह स्टैक से कभी नहीं निकलता है। नॉनडेटर्मिनिस्टिक, नॉनरेज़िंग स्टैक ऑटोमेटा द्वारा स्वीकृत लैंग्वेज का वर्ग [[NSPACE]](n) है<sup>2</sup>), जो संदर्भ-संवेदनशील लैंग्वेज#कम्प्यूटेशनल गुणों|संदर्भ-संवेदनशील लैंग्वेज का सुपरसेट है।<ref name="Hopcroft.Ullman.1967">{{cite journal|author1=John E. Hopcroft |author2=Jeffrey D. Ullman | title=नॉनरेज़िंग स्टैक ऑटोमेटा| journal=Journal of Computer and System Sciences| year=1967| volume=1| number=2| pages=166–186| doi=10.1016/s0022-0000(67)80013-8| doi-access=free}}</ref> डीटरमिनिस्ट, नॉनरेज़िंग स्टैक ऑटोमेटा द्वारा स्वीकृत लैंग्वेज का वर्ग [[DSPACE]](n⋅log(n)) है।<ref name="Hopcroft.Ullman.1967"/>
 ==वैकल्पिक पुशडाउन ऑटोमेटा==
-एक वैकल्पिक पुशडाउन ऑटोमेटन (एपीडीए) राज्य सेट के साथ पुशडाउन ऑटोमेटन है
+एक वैकल्पिक पुशडाउन ऑटोमेटन (एपीडीए) स्थिति सेट के साथ पुशडाउन ऑटोमेटन है
 * <math>Q=Q_\exists \cup Q_\forall</math> कहाँ <math>Q_\exists \cap Q_\forall=\emptyset</math>.
-राज्यों में <math>Q_\exists</math> और <math>Q_\forall</math> अस्तित्वगत सम्मान कहलाते हैं। सार्वभौमिक। अस्तित्वगत स्थिति में एपीडीए गैर-नियतात्मक रूप से अगले राज्य को चुनता है और स्वीकार करता है यदि परिणामी गणनाओं में से कम से कम स्वीकार करता है। सार्वभौमिक स्थिति में APDA सभी अगले राज्यों में चला जाता है और यदि सभी परिणामी गणनाएँ स्वीकार हो जाती हैं तो स्वीकार करता है।
+स्थितिों में <math>Q_\exists</math> और <math>Q_\forall</math> अस्तित्वगत सम्मान कहलाते हैं। सार्वभौमिक। अस्तित्वगत स्थिति में एपीडीए गैर-डीटरमिनिस्ट रूप से अगले स्थिति को चुनता है और स्वीकार करता है यदि परिणामी गणनाओं में से कम से कम स्वीकार करता है। सार्वभौमिक स्थिति में APDA सभी अगले स्थितिों में चला जाता है और यदि सभी परिणामी गणनाएँ स्वीकार हो जाती हैं तो स्वीकार करता है।
-मॉडल को अशोक के. चंद्रा, [[डेक्सटर कोज़ेन]] और [[लैरी स्टॉकमेयर]] द्वारा पेश किया गया था।<ref name="ChandraKozen1981">{{cite journal|last1=Chandra|first1=Ashok K.|last2=Kozen|first2=Dexter C.|last3=Stockmeyer|first3=Larry J.|title=अदल-बदल|journal=Journal of the ACM|volume=28|issue=1|year=1981|pages=114–133|issn=0004-5411|doi=10.1145/322234.322243}}</ref> रिचर्ड ई. लैडनर, रिचर्ड जे. लिप्टन और लैरी स्टॉकमेयर<ref name="LadnerLipton1984">{{cite journal|last1=Ladner|first1=Richard E.|last2=Lipton|first2=Richard J.|last3=Stockmeyer|first3=Larry J.|title=वैकल्पिक पुशडाउन और स्टैक ऑटोमेटा|journal=SIAM Journal on Computing|volume=13|issue=1|year=1984|pages=135–155|issn=0097-5397|doi=10.1137/0213010}}</ref> साबित हुआ कि यह मॉडल [[EXPTIME]] के बराबर है यानी भाषा कुछ APDA द्वारा स्वीकार की जाती है यदि, और केवल तभी, इसे घातीय-समय एल्गोरिदम द्वारा तय किया जा सकता है।
+मॉडल को अशोक के. चंद्रा, [[डेक्सटर कोज़ेन]] और [[लैरी स्टॉकमेयर]] द्वारा पेश किया गया था।<ref name="ChandraKozen1981">{{cite journal|last1=Chandra|first1=Ashok K.|last2=Kozen|first2=Dexter C.|last3=Stockmeyer|first3=Larry J.|title=अदल-बदल|journal=Journal of the ACM|volume=28|issue=1|year=1981|pages=114–133|issn=0004-5411|doi=10.1145/322234.322243}}</ref> रिचर्ड ई. लैडनर, रिचर्ड जे. लिप्टन और लैरी स्टॉकमेयर<ref name="LadnerLipton1984">{{cite journal|last1=Ladner|first1=Richard E.|last2=Lipton|first2=Richard J.|last3=Stockmeyer|first3=Larry J.|title=वैकल्पिक पुशडाउन और स्टैक ऑटोमेटा|journal=SIAM Journal on Computing|volume=13|issue=1|year=1984|pages=135–155|issn=0097-5397|doi=10.1137/0213010}}</ref> साबित हुआ कि यह मॉडल [[EXPTIME]] के बराबर है यानी लैंग्वेज कुछ APDA द्वारा स्वीकार की जाती है यदि, और मात्र तभी, इसे घातीय-समय एल्गोरिदम द्वारा निर्धारित किया जा सकता है।
-ऐज़िकोविट्ज़ और कमिंसकी<ref name="AizikowitzKaminski2011">{{cite book|last1=Aizikowitz|first1=Tamar|title=Computer Science – Theory and Applications|last2=Kaminski|first2=Michael|chapter=LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata|volume=6651|year=2011|pages=345–358|issn=0302-9743|doi=10.1007/978-3-642-20712-9_27|series=Lecture Notes in Computer Science|isbn=978-3-642-20711-2}}</ref> सिंक्रोनाइज्ड अल्टरनेटिंग पुशडाउन ऑटोमेटा (एसएपीडीए) पेश किया गया जो कि [[संयोजक व्याकरण]] के समतुल्य है, उसी तरह जैसे गैर-नियतात्मक पीडीए संदर्भ-मुक्त व्याकरण के समतुल्य है।
+ऐज़िकोविट्ज़ और कमिंसकी<ref name="AizikowitzKaminski2011">{{cite book|last1=Aizikowitz|first1=Tamar|title=Computer Science – Theory and Applications|last2=Kaminski|first2=Michael|chapter=LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata|volume=6651|year=2011|pages=345–358|issn=0302-9743|doi=10.1007/978-3-642-20712-9_27|series=Lecture Notes in Computer Science|isbn=978-3-642-20711-2}}</ref> सिंक्रोनाइज्ड अल्टरनेटिंग पुशडाउन ऑटोमेटा (एसएपीडीए) पेश किया गया जो कि [[संयोजक व्याकरण]] के समतुल्य है, उसी प्रकार जैसे गैर-डीटरमिनिस्ट पीडीए संदर्भ-मुक्त व्याकरण के समतुल्य है।
 ==यह भी देखें==
@@ Line 189: / Line 188: @@
 <references/>
 * {{cite book | author = Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X | author-link = Michael Sipser | url-access = registration | url = https://archive.org/details/introductiontoth00sips }} Section 2.2: Pushdown Automata, pp.&nbsp;101&ndash;114.
-* Jean-Michel Autebert, Jean Berstel, Luc Boasson, [http://www-igm.univ-mlv.fr/~berstel/Articles/1997CFLPDA.pdf Context-Free Languages and Push-Down Automata], in: G. Rozenberg, A. Salomaa (eds.), Handbook of Formal Languages, Vol. 1, Springer-Verlag, 1997, 111–174.
+* Jean-Michel Autebert, Jean Berstel, Luc Boasson, [http://www-igm.univ-mlv.fr/~berstel/Articles/1997CFLPDA.pdf Context-Free लैंग्वेजs and Push-Down Automata], in: G. Rozenberg, A. Salomaa (eds.), Handbook of Formal लैंग्वेजs, Vol. 1, Springer-Verlag, 1997, 111–174.
 ==बाहरी संबंध==
 * [https://www.jflap.org JFLAP], simulator for several types of automata including nondeterministic pushdown automata

Anonymous

Search

पुशडाउन ऑटोमेटन: Difference between revisions

Namespaces

More

Page actions

Revision as of 00:10, 26 July 2023

Contents

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

उदाहरण

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

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

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

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

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

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

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

पुशडाउन ऑटोमेटन: Difference between revisions

Revision as of 00:10, 26 July 2023

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

उदाहरण

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

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

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

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

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

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

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories