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

Pushdown Automata (PDA) और Context-Free Grammar (CFG) दोनों Context-Free Languages (CFLs) को परिभाषित करने के दो समकक्ष (equivalent) मॉडल हैं। हम पहले से जानते हैं कि हर CFG के लिए एक NPDA बनाया जा सकता है जो उसी भाषा को पहचानता है। इसी तरह, हर NPDA के लिए एक CFG बनाई जा सकती है जो वही भाषा उत्पन्न करती है। इस लेख में हम NPDA → CFG रूपांतरण की प्रक्रिया को विस्तार से समझेंगे।

परिचय / Introduction

NPDA से CFG में रूपांतरण यह दर्शाता है कि Context-Free Grammar और Pushdown Automata समान computational शक्ति रखते हैं। इस रूपांतरण से यह सिद्ध होता है कि PDA केवल Context-Free Languages को पहचान सकता है और इन भाषाओं के लिए Grammar हमेशा मौजूद होती है।

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

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

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

जहाँ:

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

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

CFG को 4-tuple के रूप में लिखा जाता है:

G = (V, Σ, R, S)

जहाँ:

• V → Variables या Non-terminals
• Σ → Terminals का set
• R → Production rules
• S → Start symbol

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

यह रूपांतरण इस बात को सिद्ध करता है कि हर PDA को CFG द्वारा represent किया जा सकता है। CFG और NPDA दोनों Context-Free Languages को परिभाषित करते हैं लेकिन विभिन्न दृष्टिकोण से — Grammar language को generate करती है जबकि PDA उसे recognize करता है।

4️⃣ मूल विचार / Main Idea

हम प्रत्येक pair of states (p, q) और Stack symbol A के लिए एक Grammar variable [pAq] बनाएँगे। यह variable उन सभी strings को represent करता है जो PDA को state p से q तक ले जाती हैं जबकि Stack में A symbol को consume करती हैं।

5️⃣ रूपांतरण के चरण / Steps for Conversion

1. NPDA = (Q, Σ, Γ, δ, q₀, Z₀, F) लें।
2. हर (p, A, q) के लिए एक variable [pAq] बनाएँ।
3. Transitions को Grammar rules में परिवर्तित करें:

Rule 1: Push Transition

यदि δ(p, a, A) में Stack पर symbols γ₁γ₂...γₙ push किए जाते हैं, तो Grammar rule होगा:

[pAq] → a [r₁γ₁r₂][r₂γ₂r₃]...[rₙγₙq]

Rule 2: Pop Transition

यदि δ(p, a, A) = (q, ε) है, तो:

[pAq] → a

Rule 3: ε-Transition

यदि δ(p, ε, A) = (q, ε), तो:

[pAq] → ε

6️⃣ Start Symbol / Starting Variable

यदि PDA का प्रारंभिक state q₀ और final state q_f है, और Stack का प्रारंभिक symbol Z₀ है, तो Grammar का Start Symbol होगा:

S = [q₀Z₀q_f]

7️⃣ उदाहरण / Example

Consider NPDA for L = {aⁿbⁿ | n ≥ 1}

Transitions:

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

Grammar Construction:

• Variables: [q₀Aq₁], [q₀Z₀q₁], [q₀Aq₀]
• Start Variable: [q₀Z₀q_f]

Production Rules:

[q₀Z₀q_f] → a [q₀Aq₀] [q₀Z₀q_f] b | ab
[q₀Aq₀] → a [q₀Aq₀] b | ab

यह Grammar वही भाषा generate करती है जो NPDA recognize करता है।

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

Grammar किसी String को generate करती है ⇔ NPDA उसी String को accept करता है। इसलिए यह रूपांतरण context-free भाषाओं की equivalence को स्थापित करता है।

9️⃣ CFG निर्माण के लाभ / Advantages

• Formal verification के लिए CFG representation आवश्यक है।
• Parsing और Syntax checking आसान होता है।
• Compiler और Automata analysis में उपयोगी।

🔟 निष्कर्ष / Conclusion

NPDA से CFG में रूपांतरण यह सिद्ध करता है कि CFG और PDA समान computational क्षमता रखते हैं। Grammar language को generate करती है, जबकि PDA उसे recognize करता है। इस equivalence से Context-Free Languages की सीमाएँ और शक्तियाँ दोनों स्पष्ट होती हैं।