Normal Forms of CFG (CNF and GNF) | प्रसंग-मुक्त व्याकरण के सामान्य रूप (CNF और GNF)

Context-Free Grammar (CFG) को व्यवस्थित रूप में प्रस्तुत करने के लिए इसे Normal Forms में रूपांतरित किया जाता है। यह रूप CFG को Parsing और Syntax Analysis के लिए उपयुक्त बनाते हैं। सबसे अधिक उपयोग किए जाने वाले Normal Forms हैं — Chomsky Normal Form (CNF) और Greibach Normal Form (GNF)।

परिचय / Introduction

CFG को Simplify और Standardize करने के लिए CNF और GNF का उपयोग किया जाता है। यह रूप Parsing Algorithms (जैसे CYK Algorithm) में उपयोगी होते हैं और Grammar की जटिलता को घटाते हैं।

1️⃣ Chomsky Normal Form (CNF) / चॉम्स्की सामान्य रूप

Chomsky Normal Form (CNF) में हर Production Rule निम्नलिखित दो रूपों में होता है:

A → BC
A → a

जहाँ:

• A, B, C Non-terminals हैं।
• ‘a’ Terminal symbol है।

CNF के नियम / CNF Rules

• ε-productions नहीं होने चाहिए (सिवाय Start Symbol के)।
• Unit Productions (A → B) नहीं होने चाहिए।
• हर RHS या तो दो Non-terminals या एक Terminal से बना हो।

उदाहरण / Example

Grammar:

S → ASA | aB
A → B | S
B → b

Step 1: Null Productions हटाएँ

S → ASA | AS | SA | aB | a
A → B | S
B → b

Step 2: Unit Productions हटाएँ

A → b | ASA | aB | a

Step 3: CNF में रूपांतरण

S → AB | a
A → BC | b
B → a
C → SB

2️⃣ CNF रूपांतरण की प्रक्रिया / Steps to Convert CFG into CNF

1. Null (ε) productions हटाएँ।
2. Unit productions हटाएँ।
3. Useless symbols हटाएँ।
4. हर rule को A → BC या A → a के रूप में बदलें।

उदाहरण:

S → AB | a
A → a
B → b

3️⃣ CNF के लाभ / Advantages of CNF

• Parsing आसान होता है।
• CYK Algorithm जैसे Parsing Algorithms के लिए आवश्यक।
• Grammar Validation सरल होती है।

4️⃣ Greibach Normal Form (GNF) / ग्रेबैक सामान्य रूप

Greibach Normal Form (GNF) में हर Production Rule इस प्रकार होता है:

A → aα

जहाँ:

• ‘a’ एक Terminal Symbol है।
• α शून्य या अधिक Non-terminals का अनुक्रम है।

GNF की विशेषताएँ / Properties of GNF

• हर Production एक Terminal Symbol से शुरू होता है।
• ε-productions नहीं होतीं।
• Top-Down Parsing के लिए उपयुक्त।

उदाहरण / Example

Grammar:

S → AB | b
A → aA | a
B → bB | ε

GNF में रूपांतरण के बाद:

S → b | aAB | ab
A → aA | a
B → bB | b

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

1. Left recursion हटाएँ।
2. CNF में Grammar परिवर्तित करें।
3. हर Rule को Terminal Symbol से प्रारंभ करें।

6️⃣ CNF और GNF में अंतर / Difference Between CNF and GNF

पहलू	CNF	GNF
Rule Structure	A → BC या A → a	A → aα
Parsing Type	Bottom-Up Parsing	Top-Down Parsing
Use	CYK Algorithm	LL Parser
ε-Productions	नहीं होतीं	नहीं होतीं
Initial Symbol	Terminal या दो Non-terminals	हमेशा Terminal

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

• Compiler Design में Syntax Checking।
• Parsing Algorithms (CYK, LL, LR) में।
• Formal Verification में।

🔟 निष्कर्ष / Conclusion

CNF और GNF दोनों Context-Free Grammar के Standard Forms हैं जो Parsing और Language Recognition को सरल बनाते हैं। जहाँ CNF Bottom-Up Parsing के लिए उपयुक्त है, वहीं GNF Top-Down Parsing के लिए प्रयोग किया जाता है। इन रूपों से Grammar को Standardized और Machine-readable बनाया जा सकता है।