Conversion of CFG to NPDA | CFG से NPDA में रूपांतरण

Context-Free Grammar (CFG) भाषाओं को generate करने के लिए उपयोग होती है जबकि Pushdown Automata (PDA) उन्हीं भाषाओं को recognize करने के लिए उपयोग होती है। जब PDA को Non-Deterministic रूप में बनाया जाता है, तो उसे NPDA कहा जाता है। इस लेख में हम सीखेंगे कि कैसे किसी CFG को उसके equivalent NPDA में परिवर्तित किया जाता है।

परिचय / Introduction

CFG और NPDA एक-दूसरे के equivalent computational models हैं। हर CFG के लिए एक NPDA मौजूद होता है जो उसी भाषा को पहचान सकता है जिसे CFG generate करती है। यह रूपांतरण Language Theory और Compiler Design दोनों में उपयोगी है।

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

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

G = (V, Σ, R, S)

जहाँ:

• V → Variables या Non-terminals
• Σ → Terminals का सेट
• R → Production Rules
• S → Start Symbol

Example:

S → aSb | ε

2️⃣ NPDA की परिभाषा / Definition of NPDA

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

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

जहाँ:

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

3️⃣ CFG से NPDA में रूपांतरण का उद्देश्य / Objective of Conversion

इस रूपांतरण का उद्देश्य यह सिद्ध करना है कि CFG द्वारा generate की गई हर Context-Free Language NPDA द्वारा भी recognize की जा सकती है।

4️⃣ रूपांतरण का सिद्धांत / Conversion Principle

हम एक ऐसा NPDA बनाते हैं जो Stack पर CFG के symbols को simulate करता है। जब भी Stack के शीर्ष पर कोई Non-terminal होता है, तो PDA उस पर Grammar rule लागू करता है। जब Stack के शीर्ष पर कोई Terminal होता है, तो उसे Input symbol से match किया जाता है।

5️⃣ रूपांतरण की प्रक्रिया / Steps for Conversion

1. Stack में Start Symbol push करें।
2. यदि Stack के शीर्ष पर कोई Non-terminal हो → उस पर Grammar Rule लागू करें।
3. यदि Stack के शीर्ष पर कोई Terminal हो → उसे Input से match करें और pop करें।
4. यदि Stack खाली हो और Input समाप्त हो जाए → String स्वीकार करें।

Transition Function Representation:

δ(q, ε, A) = (q, α)

यहाँ A → α Grammar का Production Rule है।

6️⃣ उदाहरण / Example

Grammar:

S → aSb | ε

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

NPDA Design:

• जब Stack में S हो → Replace it using Grammar rule।
• जब Input ‘a’ हो → Stack में ‘a’ push करें।
• जब Input ‘b’ हो → Stack से ‘a’ pop करें।
• यदि Stack खाली हो → Accept करें।

Transitions:

δ(q, ε, S) = (q, aSb)
δ(q, ε, S) = (q, ε)
δ(q, a, a) = (q, ε)
δ(q, b, b) = (q, ε)

Explanation:

• पहले Transition Grammar rule S → aSb को लागू करता है।
• दूसरा Transition ε-production के लिए है।
• तीसरा और चौथा Transition Input symbols को match करते हैं।

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

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

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

8️⃣ CFG से NPDA Conversion Algorithm / Algorithm

1. Create NPDA M = (Q, Σ, Γ, δ, q₀, Z₀, F).
2. Initialize: Stack with Start Symbol S.
3. For every production A → α, add transition δ(q, ε, A) = (q, α).
4. For each terminal symbol a, add δ(q, a, a) = (q, ε).
5. If Stack empty and input consumed → Accept.

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

• Compiler Design में Grammar validation।
• Syntax Analysis automation।
• Formal Language equivalence proofs में।

🔟 निष्कर्ष / Conclusion

CFG से NPDA में रूपांतरण यह सिद्ध करता है कि Grammar और Automata समान computational शक्ति रखते हैं। यह सिद्धांत Automata Theory का मूल है और Compiler Parsing के कार्य में PDA का आधार बनाता है।