Simplification of context free grammar in Hindi

Unit 3

Grammars

Topic 4 : Simplification of context free grammar in Hindi :

CFG context free grammar में, ऐसा हो सकता है कि string के derivation के लिए सभी production rules और symbols की आवश्यकता नहीं है। इसके अलावा, कुछ null productions और unit productions हो सकते हैं। इन productions और Symbol के Elimination को CFG का Simplification कहा जाता है। Simplification अनिवार्य रूप से निम्नलिखित चरणों में शामिल है -

Reduction of CFG
Removal of Unit Productions
Removal of Null Productions

Reduction of CFG :

CFG दो phases में reduced हो जाते हैं

Phase 1 − CFG, G से एक equivalent grammar, G 'की Derivation, जैसे कि प्रत्येक variable कुछ terminal string को प्राप्त करता है।

Derivation Procedure –

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 कहा जाता है

Removal Procedure −

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 → .......… → ε

Removal Procedure

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 को हटा दें।