Unknown
CFG context free grammar में, ऐसा हो सकता है कि string के derivation के लिए सभी production rules और symbols की आवश्यकता नहीं है। इसके अलावा, कुछ null productions और unit productions हो सकते हैं। इन productions और Symbol के Elimination को CFG का Simplification कहा जाता है। Simplification अनिवार्य रूप से निम्नलिखित चरणों में शामिल है -
CFG दो phases में reduced हो जाते हैं
Phase 1 − CFG, G से एक equivalent grammar, G 'की Derivation, जैसे कि प्रत्येक variable कुछ terminal string को प्राप्त करता है।
Step 1 − W1, सभी Symbols को शामिल करें, जो कुछ terminal प्राप्त करते हैं और i = 1 को initialize करते हैं
Step 2 − सभी Symbol को शामिल करें, Wi+1, जो Wi को प्राप्त करता है।
Step 3 − Increment i और repeat Step 2, जब तक Wi+1 = Wi. ।
Step 4 − उन सभी production rules को include करें जिनमें Wi है।
Phase 2 − CFG, G 'से एक समान grammar, G " का Derivation, जैसे कि प्रत्येक Symbol एक sentential form में दिखाई देता है।
Derivation Procedure −
Step 1 − Y1 में start symbol मे शामिल करें और i = 1 को initialize करें
Step 2 − सभी symbol को include करें, Yi+1, जिसे Yi से प्राप्त किया जा सकता है और इसमें सभी production rules include हैं जो लागू किए गए हैं।
Step 3 − Increment I और repeat Step 2, जब तक Yi+1 = Yi ।
Removal of Unit Productions
A → B के रूप में कोई भी उत्पादन नियम जहां A, B terminal Non- terminal को unit production कहा जाता है
Step 1 : A → B को निकालने के लिए, जब भी B → x grammar में होता है, तो production A → x को grammar rule में जोड़ें। [x ∈ terminal, x Null हो सकता है ]
Step 2 : A → B को grammar से Delete करे
Step 3 : step 1 से Repeat करे । जब तक सभी unit productions को delete कर दिया जाता है।
Removal of Null Productions :
CFG में, एक non-terminal symbol A ’एक nullable variable है यदि production A → ε है या एक derivation है जो A पर Start होती है और last में end होती है
ε: A → .......… → ε
Step 1 − nullable non-terminal variables का FInd करे,
Step 2 − प्रत्येक production A → a के लिए, सभी production A → x का निर्माण करें जहां Step 1 से एक या कई non-terminals को हटाकर x को A से प्राप्त किया जाता है।
Step 3 − Step 2 के Result के साथ original productions को मिलाएं और। ε – productions को हटा दें।