Relationship Between PDA and Context-Free Grammar | PDA और प्रसंग-मुक्त व्याकरण का संबंध

Pushdown Automata (PDA) और Context-Free Grammar (CFG) के बीच एक गहरा और प्रत्यक्ष संबंध होता है। यह संबंध औपचारिक भाषाओं के अध्ययन में बहुत महत्वपूर्ण है क्योंकि PDA वही भाषाएँ पहचानता है जिन्हें CFG generate करती है। अर्थात —

“हर Context-Free Grammar के लिए एक Equivalent PDA होता है, और हर PDA के लिए एक Equivalent Context-Free Grammar होती है।”

परिचय / Introduction

Context-Free Grammar भाषाओं को generate करती है जबकि Pushdown Automata उन्हें recognize करता है। यह संबंध Compiler Design, Parsing और Automata Theory में मूलभूत भूमिका निभाता है।

1️⃣ Context-Free Grammar (CFG) का पुनरावलोकन / Review

CFG एक ऐसी Grammar होती है जिसमें हर production rule इस रूप में होता है:

A → α

जहाँ A एक Non-terminal और α Terminals और Non-terminals का मिश्रण होता है। CFG Context-Free Languages (CFL) को generate करती है।

उदाहरण:

S → aSb | ε

यह grammar भाषा L = {aⁿbⁿ | n ≥ 0} को generate करती है।

2️⃣ Pushdown Automata (PDA) का पुनरावलोकन / Review

PDA एक Finite Automata की तरह है लेकिन इसमें एक अतिरिक्त Stack memory होती है। Stack PDA को nested या recursive संरचनाओं को पहचानने में सक्षम बनाता है। इसलिए, PDA सभी Context-Free Languages को पहचान सकता है।

3️⃣ PDA और CFG के बीच समानता / Equivalence Between PDA and CFG

हर Context-Free Grammar के लिए एक Equivalent PDA बनाया जा सकता है जो वही भाषा पहचानता है। और हर PDA के लिए एक Equivalent CFG बनाई जा सकती है जो वही भाषा generate करती है।

Mathematical Representation:

L(PDA) = L(CFG)

अर्थात दोनों समान प्रकार की भाषाओं (CFLs) को परिभाषित करते हैं।

4️⃣ CFG → PDA रूपांतरण / Conversion from CFG to PDA

CFG को PDA में रूपांतरित करने के लिए निम्न चरण अपनाए जाते हैं:

1. Stack में Start Symbol डालें।
2. यदि Stack के शीर्ष पर कोई Non-terminal हो, तो उसे Grammar के नियमों के अनुसार Replace करें।
3. यदि Stack के शीर्ष पर कोई Terminal हो, तो उसे इनपुट Symbol से मिलाएँ।
4. यदि Stack खाली हो जाए और इनपुट समाप्त हो जाए, तो String स्वीकार करें।

उदाहरण:

Grammar:

S → aSb | ε

इसके Equivalent PDA:

• Stack पर S push करें।
• यदि Stack के शीर्ष पर S हो और इनपुट ‘a’ पढ़ा जाए, तो ‘Sb’ push करें।
• यदि Stack के शीर्ष पर ‘a’ या ‘b’ हो, तो इनपुट से मिलाएँ और pop करें।
• यदि Stack खाली हो जाए → Accept करें।

Transitions:

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

5️⃣ PDA → CFG रूपांतरण / Conversion from PDA to CFG

हर PDA के लिए एक Context-Free Grammar बनाई जा सकती है जो वही भाषा generate करती है। इस प्रक्रिया में PDA की states और stack symbols का उपयोग Grammar rules बनाने के लिए किया जाता है।

Algorithm:

• PDA के प्रत्येक (p, A, q) pair के लिए एक variable A_pq बनाएँ।
• यदि δ(p, a, A) = (r, γ) है, तो Grammar में rule बनाएँ:

A_pq → aA_pr₁A_r₁r₂ ... A_rₙq

Example:

PDA for L = {aⁿbⁿ}:

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

Equivalent Grammar:

S → aSb | ab

6️⃣ CFG और PDA की तुलना / Comparison Between CFG and PDA

पहलू	Context-Free Grammar (CFG)	Pushdown Automata (PDA)
उद्देश्य	Language Generate करना	Language Recognize करना
Model Type	Top-Down Model	Bottom-Up Model
Representation	Rules द्वारा	Transitions द्वारा
Example	S → aSb | ε	δ(q, ε, S) = (q, aSb)

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

• Compiler Design में Syntax Analysis।
• Programming Languages के Grammar validation में।
• Parsing Algorithms (LL, LR) के निर्माण में।
• Formal Verification में CFG-PDA equivalence का उपयोग।

8️⃣ महत्वपूर्ण तथ्य / Key Observations

• हर CFG → PDA के लिए संभव है।
• हर PDA → CFG के लिए संभव है।
• दोनों Context-Free Languages को ही संभालते हैं।

निष्कर्ष / Conclusion

Pushdown Automata और Context-Free Grammar के बीच का संबंध औपचारिक भाषा सिद्धांत का मूल है। CFG भाषा उत्पन्न करती है और PDA उसे पहचानता है। दोनों एक-दूसरे के पूरक हैं और Compiler Design व Syntax Analysis की नींव इन्हीं पर आधारित है।