Introduction and Example of Pushdown Automata (PDA) | पुशडाउन ऑटोमाटा का परिचय और उदाहरण

पुशडाउन ऑटोमाटा (Pushdown Automata - PDA) ऑटोमाटा सिद्धांत (Automata Theory) की एक अत्यंत महत्वपूर्ण मशीन है। यह Finite Automata की तुलना में अधिक शक्तिशाली है क्योंकि यह Stack Memory का उपयोग करती है। PDA उन भाषाओं को पहचानने के लिए प्रयुक्त होती है जिन्हें Context-Free Grammar (CFG) द्वारा उत्पन्न किया जा सकता है।

परिचय / Introduction

Pushdown Automata एक Finite Automata के समान है लेकिन इसमें एक अतिरिक्त डेटा संरचना — Stack होती है। Stack का उपयोग symbols को अस्थायी रूप से संग्रहित करने और आवश्यकतानुसार निकालने के लिए किया जाता है। इससे PDA recursive संरचनाओं (जैसे aⁿbⁿ) को पहचान सकती है, जो Finite Automata नहीं कर सकता।

1️⃣ PDA की औपचारिक परिभाषा / Formal Definition of PDA

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

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

• Q → States का finite set
• Σ → Input alphabet
• Γ → Stack alphabet
• δ → Transition function
• q₀ → Initial state
• Z₀ → Initial stack symbol
• F → Final states का set

Transition function δ का स्वरूप होता है:

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

2️⃣ PDA के घटक / Components of PDA

• Input Tape: जहाँ इनपुट string होती है।
• Control Unit: जो transitions को नियंत्रित करता है।
• Stack: एक LIFO (Last In First Out) डेटा संरचना, जो symbols को संग्रहित करता है।

3️⃣ PDA की कार्यप्रणाली / Working of PDA

PDA का कार्य इस प्रकार होता है:

1. Input symbol को पढ़ा जाता है।
2. Stack के शीर्ष symbol को देखा जाता है।
3. Transition function के आधार पर नया state और stack की स्थिति निर्धारित की जाती है।
4. जब पूरा इनपुट पढ़ लिया जाता है और stack खाली हो जाता है या final state पहुँच जाती है, तो PDA उस string को स्वीकार करता है।

4️⃣ Example: Language L = {aⁿbⁿ | n ≥ 1}

यह भाषा उन strings को स्वीकार करती है जिनमें 'a' की संख्या 'b' की संख्या के बराबर होती है। Finite Automata इस भाषा को नहीं पहचान सकता, लेकिन PDA कर सकता है।

Grammar:

S → aSb | ab

PDA Design:

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

Formal Definition:

Q = {q₀, q₁, q₂}
Σ = {a, b}
Γ = {A, Z₀}
q₀ = Start state
Z₀ = Initial stack symbol
F = {q₂}

Transitions:

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

यह PDA केवल उन्हीं strings को स्वीकार करेगा जिनमें a की संख्या b के बराबर होगी।

5️⃣ PDA द्वारा स्वीकृति / Acceptance by PDA

PDA किसी string को दो तरीकों से स्वीकार कर सकता है:

• Final State Acceptance: जब पूरा इनपुट पढ़ने के बाद PDA एक final state में पहुँच जाता है।
• Empty Stack Acceptance: जब PDA का stack खाली हो जाता है।

6️⃣ PDA के प्रकार / Types of PDA

• Deterministic PDA (DPDA): जहाँ प्रत्येक इनपुट और stack symbol के लिए केवल एक ही transition होता है।
• Non-Deterministic PDA (NPDA): जहाँ किसी एक स्थिति के लिए एक से अधिक transitions संभव होते हैं।

7️⃣ PDA की सीमाएँ / Limitations

• PDA केवल Context-Free Languages को पहचान सकता है।
• यह Context-Sensitive Languages को नहीं पहचान सकता।
• Parsing ambiguity को हटाने के लिए सीमित सहायता देता है।

8️⃣ PDA का उपयोग / Applications of PDA

• Compiler Design में Parsing के लिए।
• Programming Language Syntax Checking में।
• Mathematical Expression Evaluation में।
• XML/HTML Tag Validation में।

निष्कर्ष / Conclusion

Pushdown Automata, Finite Automata से अधिक शक्तिशाली मशीन है जो Stack का उपयोग कर recursive संरचनाओं को पहचान सकती है। यह Context-Free Languages की पहचान का आधार है और Compiler Design के लिए अत्यंत आवश्यक अवधारणा है।