Pushdown automata, stacks और acceptance
लक्ष्य और acceptance contract
Unbounded counts मिलाने के लिए stack उपयोग करें और CFG–PDA संबंध समझें। अलग से न कहा हो तो PDA का अर्थ nondeterministic PDA, अर्थात NPDA है। Configuration (q,w,γ) में state, unread input और stack हैं। Stack top बाईं ओर लिखते हैं। (q,a,X)→(r,β) में a consume, X pop और β से replace होता है; a=ε होने पर input consume नहीं होता। यदि γ=Xη है तो नया stack βη होगा। ये notation conventions हैं।
Final-state acceptance में कोई finite computation पूरा input consume करके final state में खत्म हो; stack कुछ भी हो सकता है। Empty-stack acceptance में पूरा input consume होकर stack खाली हो; state कोई भी हो सकती है। Input बचा हो तो final state या empty stack पर्याप्त नहीं। NPDAs में suitable conversions से दोनों modes ठीक CFLs देते हैं; उसी unchanged machine पर दोनों modes समान होना जरूरी नहीं।
1. a^n b^n का worked NPDA
Z bottom marker, A count marker और push,pop,accept states लें। Start push में stack Z है। Push mode में हर a पर A जोड़ें: X को AX करें, X=A या Z। पहले b पर pop mode में जाएँ और एक A हटाएँ। Pop में हर b एक A हटाता है; a-transition नहीं है। Z दिखने पर ε-move से accept जा सकते हैं। ε accept करने के लिए push से Z पर भी यह move दें। Accept state से कोई outgoing transition नहीं। Final-state acceptance केवल पूरा input consume होने पर है।
aabb trace: (push,aabb,Z)→(push,abb,AZ)→(push,bb,AAZ)→(pop,b,AZ)→(pop,ε,Z)→(accept,ε,Z)। aab में एक A बचता है, इसलिए accept नहीं। abb में दूसरे b को Z मिलता है और matching pop नहीं है। aba में pop mode का a consume नहीं हो सकता। Push से Z पर early ε-move किसी nonempty word को गलत accept नहीं करता, क्योंकि input बचा है।
Invariant: push mode में stack पढ़े गए a गिनता है; pop mode में b phase शुरू होने के बाद unmatched a गिनता है। पूरा input पढ़कर Z मिलना equal counts देता है; phases a-block के बाद b-block का क्रम सुनिश्चित करते हैं।
2. Midpoint guess करना
Even palindromes {ww^R:w∈{0,1}*} के लिए NPDA पहले segment को push करता है, ε-move से उसका अंत nondeterministically guess करता है, फिर बाकी input को stack top से match करके pop करता है। पूरा input consume और bottom मिलने पर accept। गलत guess fail हो सकता है; सही accepting guess ठीक palindrome के लिए मौजूद है। Marked language {w#w^R} में # switch करने का बिंदु बताता है, इसलिए deterministic stack strategy चलती है। Unmarked input में “बीच पर switch करें” कहना deterministic online algorithm नहीं है; बीच की position दी नहीं गई है।
3. CFG को stack से simulate करें
शुरू में start variable stack पर रखें। Top A variable हो तो कोई production चुनकर बिना input पढ़े उसके right side से replace करें। Top terminal a हो तो input a match करके दोनों consume/pop करें। पूरा input consume और stack empty होने पर accept। Top left convention में A→XYZ से X top बनता है; एक-एक symbol push करने वाला implementation Z,Y,X क्रम से push करेगा।
S→aSb|ε और input ab में stack S से aSb बने; a match करने पर Sb; S→ε से b; b match करने पर empty। यह leftmost derivation simulate करता है। उलटी दिशा में PDA से CFG बनती है जिसकी variables states के बीच stack-removal computations summarize करती हैं। दोनों translations CFG और NPDA की language equivalence देती हैं।
4. Determinism की सावधानियाँ
DPDA में एक configuration पर competing transitions नहीं हो सकतीं। खासकर किसी state/top pair पर ε-transition हो तो standard definition में उसी pair पर input-consuming transitions नहीं हो सकतीं। DPDAs, CFLs का proper subclass पहचानते हैं। Deterministic final-state तथा empty-stack modes अतिरिक्त conventions के बिना interchangeable नहीं हैं; endmarker के बिना empty-stack acceptance prefix restrictions देता है। NPDA equivalence को सीधे DPDA पर लागू न करें।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. Final-state PDA acceptance में कौन-सी condition जरूरी है?
A. Stack खाली होना चाहिए B. पूरा input consume हो और final state मिले C. हर branch accept हो D. कभी भी final state visit हो
उत्तर: B
A: Final-state mode nonempty stack भी मानता है।
B: पूरा input तथा finality दोनों जरूरी हैं।
C: NPDA acceptance existential है।
D: Unread input के साथ visit पर्याप्त नहीं।
P02. Top left होने पर XZ में X को AB से बदलने पर क्या होगा?
A. ZAB B. ABZ C. BAZ D. XZAB
उत्तर: B
A: इसमें replacement Z के नीचे है।
B: X की जगह AB, नीचे Z रहता है।
C: यह replacement उलटता है।
D: X हटना चाहिए, बचना नहीं।
P03. Worked PDA abb क्यों reject करता है?
A. A push नहीं कर सकता B. पहला b निषिद्ध है C. दूसरे b के लिए pop करने को A नहीं है D. Input length हमेशा चार होनी चाहिए
उत्तर: C
A: पहला a, A push करता है।
B: पहला b pop mode में जाकर A हटाता है।
C: दूसरे b से पहले केवल Z बचता है।
D: Length four का नियम नहीं है।
P04. w#w^R में # मुख्यतः क्या देता है?
A. |w| पर finite upper bound B. Phase बदलने का स्पष्ट बिंदु C. दूसरा stack D. हर suffix का automatic acceptance
उत्तर: B
A: w unbounded रहता है।
B: Matching शुरू करने का स्थान बताता है।
C: एक stack पर्याप्त है।
D: Reverse suffix फिर भी match करना होगा।
P05. Leftmost top पर A→XYZ के लिए individual pushes का क्रम क्या है?
A. X,Y,Z B. Z,Y,X C. Y,X,Z D. कोई क्रम इसे नहीं दर्शा सकता
उत्तर: B
A: इससे Z top पर रहेगा।
B: Reverse push से X top रहता है।
C: Z top और बाकी क्रम गलत होगा।
D: Stack right side दर्शा सकता है।
P06. Extra deterministic conventions के बिना कौन सही है?
A. सभी CFLs की DPDA होती है B. हर NPDA पहले से DPDA है C. NPDA के final-state और empty-stack modes की language-class power समान है D. DPDA finals उलटना हमेशा तुरंत complement देता है
उत्तर: C
A: DPDA proper subclass पहचानता है।
B: Nondeterministic choices जरूरी हो सकती हैं।
C: Machine conversions NPDA equivalence देती हैं।
D: Halting, input consumption और conventions का ध्यान चाहिए।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Theory of Computation syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन