Chomsky Normal Form (CNF) and Greibach Normal Form (GNF) | चॉम्स्की एवं ग्रेबैक सामान्य रूप

Context-Free Grammar (CFG) को कुछ विशेष रूपों में परिवर्तित किया जा सकता है ताकि उसे समझना और मशीन द्वारा पार्स करना आसान हो। इनमें दो प्रमुख रूप हैं — Chomsky Normal Form (CNF) और Greibach Normal Form (GNF)। ये रूप Parsing और Syntax Analysis में विशेष रूप से उपयोगी हैं।

परिचय / Introduction

CFG का सामान्य रूप (Normal Form) वह रूप है जिसमें Grammar के Production Rules कुछ निश्चित शर्तों का पालन करते हैं। CNF और GNF दोनों का उद्देश्य Grammar को Standardized और Machine-readable बनाना है।

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

CNF में प्रत्येक Production Rule निम्नलिखित दो में से किसी एक रूप में होता है:

A → BC
A → a

जहाँ A, B, C Non-terminals हैं और ‘a’ Terminal symbol है। यह भी आवश्यक है कि B और C Start Symbol न हों।

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

• Right-hand side में या तो दो Non-terminals या एक Terminal होता है।
• ε-productions और unit productions को हटाया जाता है।
• Grammar Ambiguity घटती है।

उदाहरण:

मूल 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

अब Grammar CNF में है क्योंकि प्रत्येक rule A → BC या A → a के रूप में है।

2️⃣ CNF में रूपांतरण के चरण / Steps for Conversion to CNF

1. Null Productions हटाएँ।
2. Unit Productions हटाएँ।
3. Useless Symbols हटाएँ।
4. सभी RHS को अधिकतम दो Non-terminals में विभाजित करें।

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

• Parsing Algorithms (जैसे CYK Parser) में उपयोगी।
• Grammar Validation में सरलता।
• Ambiguity कम होती है।

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

GNF में हर Production Rule निम्नलिखित रूप में होता है:

A → aα

जहाँ ‘a’ Terminal symbol है और α Zero या अधिक Non-terminals का अनुक्रम है।

उदाहरण:

Grammar:

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

GNF रूप में:

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

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

• हर Production का प्रारंभ एक Terminal से होता है।
• Grammar Ambiguity घटती है।
• Top-Down Parsing के लिए आदर्श रूप है।

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

1. Grammar को CNF में परिवर्तित करें।
2. Left Recursion हटाएँ।
3. हर rule को Terminal से शुरू करें।

उदाहरण:

A → Aa | b

Left Recursion हटाने पर:

A → bA'
A' → aA' | ε

अब GNF में पहला symbol हमेशा Terminal है।

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

Aspect	CNF	GNF
Rule Form	A → BC | a	A → aα
Start Symbol	Terminal या दो Non-terminals से प्रारंभ	हमेशा Terminal से प्रारंभ
Use	Bottom-Up Parsing	Top-Down Parsing
Preferred For	CYK Algorithm	Recursive Descent Parser

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

• Compiler Design में Syntax Analysis।
• Parsing Algorithms जैसे CYK और LL Parser में।
• Programming Language Grammar Validation।

🔟 निष्कर्ष / Conclusion

Chomsky Normal Form (CNF) और Greibach Normal Form (GNF) Context-Free Grammars को standard रूप में प्रस्तुत करने के दो मुख्य तरीके हैं। CNF Bottom-Up Parsing के लिए और GNF Top-Down Parsing के लिए अधिक उपयोगी होती है। इन रूपों का उपयोग Compiler Design, Syntax Checking और Formal Verification में व्यापक रूप से किया जाता है।