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

NP Complete Problem in Hindi

NP-Complete problems एक महत्वपूर्ण वर्ग हैं जो computational complexity the...

Multihead Turing Machine और Multidimensional Turing Machine की विशेषताएँ और अंतर

Multihead Turing Machine एक प्रकार की Turing Machine है जिसमें एक से अ�...

Universal Turing Machine and Multitape in Hindi

Universal Turing Machine (UTM) एक ऐसी ट्यूरिंग मशीन है, जो किसी भ...

Techniques for Turing Machine Construction in Hindi

Turing Machine कंप्यूटर विज्ञान में एक theoretical model है, जो क�...

Petri Net Model in Hindi | Theory of Computation (TOC) Explained

Petri Net एक mathematical model है जो systems के behavior को graphically represent करने �...

Simplification of context free grammar in Hindi