Deterministic and Non-Deterministic Pushdown Automata (DPDA vs NPDA) | नियतात्मक और अनियतात्मक पुशडाउन ऑटोमाटा

Pushdown Automata (PDA) को दो प्रकारों में वर्गीकृत किया जाता है — Deterministic PDA (DPDA) और Non-Deterministic PDA (NPDA)। दोनों प्रकार Context-Free Languages (CFL) को पहचानने में सक्षम हैं, लेकिन उनकी संरचना और कार्यप्रणाली में महत्वपूर्ण अंतर होता है।

परिचय / Introduction

DPDA और NPDA दोनों Stack आधारित मशीनें हैं जो Context-Free Languages को पहचानती हैं। लेकिन DPDA हर इनपुट के लिए केवल एक ही संभव Transition चुन सकती है, जबकि NPDA कई Transition Paths पर एक साथ काम कर सकती है।

1️⃣ Deterministic PDA (DPDA) / नियतात्मक पुशडाउन ऑटोमाटा

DPDA में हर इनपुट और Stack Symbol के लिए केवल एक ही Transition संभव होता है। अर्थात किसी भी स्थिति में PDA के पास कोई अस्पष्टता (Ambiguity) नहीं होती।

DPDA की औपचारिक परिभाषा / Formal Definition

DPDA को 7-tuple के रूप में परिभाषित किया जाता है:

M = (Q, Σ, Γ, δ, q₀, Z₀, F)

जहाँ δ एक deterministic transition function है:

δ : Q × (Σ ∪ {ε}) × Γ → Q × Γ*

DPDA की विशेषताएँ / Characteristics

• हर इनपुट और Stack Symbol के लिए अधिकतम एक Transition।
• Ambiguity का अभाव।
• Final State या Empty Stack द्वारा Acceptance।
• Implementation सरल लेकिन शक्ति सीमित।

उदाहरण / Example

Language L = {aⁿbⁿ | n ≥ 0}

यह भाषा DPDA द्वारा स्वीकार की जा सकती है:

• जब ‘a’ पढ़ें → Stack में ‘A’ push करें।
• जब ‘b’ पढ़ें → Stack से एक ‘A’ pop करें।
• यदि Stack खाली हो जाए → Accept करें।

Transitions:

δ(q₀, a, Z₀) = (q₀, AZ₀)
δ(q₀, a, A)  = (q₀, AA)
δ(q₀, b, A)  = (q₁, ε)
δ(q₁, b, A)  = (q₁, ε)
δ(q₁, ε, Z₀) = (qf, Z₀)

2️⃣ Non-Deterministic PDA (NPDA) / अनियतात्मक पुशडाउन ऑटोमाटा

NPDA में किसी एक इनपुट और Stack Symbol के लिए एक से अधिक Transition संभव होते हैं। PDA किसी भी Transition को चुन सकता है या एक साथ कई Paths पर काम कर सकता है।

NPDA की विशेषताएँ / Characteristics

• एक ही स्थिति के लिए कई transitions संभव।
• Computation कई Paths पर एक साथ।
• अधिक शक्ति (More powerful) DPDA की तुलना में।
• Ambiguity संभव है।

उदाहरण / Example

Language L = {aⁿbᵐ | n, m ≥ 0}

यह भाषा केवल NPDA द्वारा स्वीकार की जा सकती है क्योंकि PDA को नहीं पता कि ‘a’ के बाद ‘b’ कब शुरू होंगे।

Transitions:

δ(q₀, ε, Z₀) = (q₁, Z₀)
δ(q₁, a, Z₀) = (q₁, AZ₀)
δ(q₁, a, A)  = (q₁, AA)
δ(q₁, ε, A)  = (q₂, A)
δ(q₂, b, A)  = (q₂, ε)
δ(q₂, ε, Z₀) = (qf, Z₀)

यह PDA कभी भी 'a' से 'b' में स्विच कर सकता है, इसलिए यह nondeterministic है।

3️⃣ Acceptance Criteria / स्वीकृति मानदंड

• By Final State: जब PDA final state पर पहुँचे।
• By Empty Stack: जब Stack पूरी तरह खाली हो जाए।

4️⃣ DPDA और NPDA में अंतर / Difference Between DPDA and NPDA

विशेषता	DPDA	NPDA
Transition Possibility	हर इनपुट के लिए एक Transition	कई Transitions संभव
Ambiguity	नहीं होती	हो सकती है
Power	कम	अधिक
Language Type	Deterministic Context-Free	Context-Free
Acceptance	By Final State / Empty Stack	By Final State / Empty Stack
Example Language	{aⁿbⁿ}	{aⁿbᵐ}

5️⃣ Relationship Between DPDA and NPDA

DPDA, NPDA का एक subset है:

L(DPDA) ⊂ L(NPDA)

अर्थात सभी Deterministic Context-Free Languages भी Context-Free होती हैं, लेकिन सभी Context-Free Languages Deterministic नहीं होतीं।

6️⃣ व्यावहारिक उपयोग / Applications

• DPDA का उपयोग Compilers में deterministic parsing के लिए किया जाता है।
• NPDA का उपयोग theoretical computation और language analysis में।
• Programming Languages की Syntax Checking।
• Automated Parser Design में।

निष्कर्ष / Conclusion

Deterministic PDA अधिक structured और predictable होती है, जबकि Non-Deterministic PDA अधिक लचीली (flexible) और शक्तिशाली होती है। DPDA केवल कुछ Context-Free Languages को पहचान सकती है, जबकि NPDA सभी Context-Free Languages को पहचान सकती है। दोनों मिलकर Context-Free Grammar के अध्ययन की नींव हैं।