सीएफजी सरलीकरण
सीएफजी में, ऐसा हो सकता है कि स्ट्रिंग्स के व्युत्पन्न के लिए सभी उत्पादन नियमों और प्रतीकों की आवश्यकता नहीं है। इसके अलावा, कुछ अशक्त प्रोडक्शंस और यूनिट प्रोडक्शंस हो सकते हैं। इन प्रस्तुतियों और प्रतीकों का उन्मूलन कहा जाता हैsimplification of CFGs। सरलीकरण अनिवार्य रूप से निम्नलिखित चरणों में शामिल है -
- सीएफजी की कमी
- यूनिट प्रोडक्शंस को हटाना
- अशक्त निर्माण हटाना
सीएफजी की कमी
CFG दो चरणों में कम हो जाते हैं -
Phase 1 - एक समान व्याकरण की व्युत्पत्ति, G’, सीएफजी से, G, ऐसा है कि प्रत्येक चर कुछ टर्मिनल स्ट्रिंग प्राप्त करता है।
Derivation Procedure -
चरण 1 - सभी प्रतीकों को शामिल करें, W1, कि कुछ टर्मिनल प्राप्त करें और आरंभ करें i=1।
चरण 2 - सभी प्रतीकों को शामिल करें, Wi+1, कि व्युत्पन्न Wi।
चरण 3 - वृद्धि i और चरण 2 को दोहराएं, जब तक Wi+1 = Wi।
चरण 4 - सभी उत्पादन नियमों को शामिल करें जो कि हैं Wi इस में।
Phase 2 - एक समान व्याकरण की व्युत्पत्ति, G”, सीएफजी से, G’, ऐसा है कि प्रत्येक प्रतीक एक भावुक रूप में प्रकट होता है।
Derivation Procedure -
चरण 1 - प्रारंभ प्रतीक को शामिल करें Y1 और आरंभ करें i = 1।
चरण 2 - सभी प्रतीकों को शामिल करें, Yi+1, कि से प्राप्त किया जा सकता है Yi और लागू किए गए सभी उत्पादन नियमों को शामिल करें।
चरण 3 - वृद्धि i और चरण 2 को दोहराएं, जब तक Yi+1 = Yi।
मुसीबत
उत्पादन नियम वाले व्याकरण G के बराबर एक कम व्याकरण ज्ञात करें, P: S → AC | बी, ए → ए, सी → सी | बीसी, ई → एए | इ
समाधान
Phase 1 -
टी = {ए, सी, ई}
डब्ल्यू 1 = {ए, सी, ई} नियमों से ए → ए, सी → सी और ई → एए
W 2 = {A, C, E} U {S} नियम S → AC से
डब्ल्यू 3 = {ए, सी, ई, एस} यू,
डब्ल्यू 2 = डब्ल्यू 3 के बाद से , हम जी 'को प्राप्त कर सकते हैं -
जी '= {{ए, सी, ई, एस}, {ए, सी, ई}, पी, {एस}}
जहाँ P: S → AC, A →, C → c, E → AA | इ
Phase 2 -
Y 1 = {S}
Y 2 = {S, A, C} नियम S → AC से
वाई 3 = {एस, ए, सी, ए, सी} नियमों से ए → ए और सी → सी
वाई 4 = {एस, ए, सी, ए, सी}
Y 3 = Y 4 के बाद से , हम G को प्राप्त कर सकते हैं -
जी ”= {{ए, सी, एस}, {ए, सी}, पी, {एस}}
जहाँ P: S → AC, A → A, C → c
यूनिट प्रोडक्शंस को हटाना
ए → बी के रूप में कोई भी उत्पादन नियम जहां ए, बी terminal नॉन-टर्मिनल कहा जाता है unit production.।
निष्कासन प्रक्रिया -
Step 1 - दूर करना A → B, उत्पादन जोड़ें A → x जब भी व्याकरण नियम के अनुसार B → xव्याकरण में होता है। [x ∈ टर्मिनल, x अशक्त हो सकता है]
Step 2 - हटाएँ A → B व्याकरण से।
Step 3 - चरण 1 से दोहराएँ जब तक सभी इकाई प्रस्तुतियों को हटा दिया जाता है।
Problem
निम्नलिखित से इकाई उत्पादन निकालें -
S → XY, X → a, Y → Z | बी, जेड → एम, एम → एन, एन → ए
Solution -
व्याकरण में 3 इकाई निर्माण हैं -
वाई → जेड, जेड → एम, और एम → एन
At first, we will remove M → N.
N → a के रूप में, हम M → a जोड़ते हैं, और M → N को हटा दिया जाता है।
उत्पादन सेट बन जाता है
S → XY, X → a, Y → Z | बी, जेड → एम, एम → ए, एन → ए
Now we will remove Z → M.
M → a के रूप में, हम Z → a जोड़ते हैं, और Z → M को हटा दिया जाता है।
उत्पादन सेट बन जाता है
S → XY, X → a, Y → Z | बी, जेड → ए, एम → ए, एन → ए
Now we will remove Y → Z.
Z → a के रूप में, हम Y → a जोड़ते हैं, और Y → Z हटा दिया जाता है।
उत्पादन सेट बन जाता है
S → XY, X → a, Y → a | बी, जेड → ए, एम → ए, एन → ए
अब Z, M और N अप्राप्य हैं, इसलिए हम उन्हें हटा सकते हैं।
अंतिम सीएफजी इकाई उत्पादन मुक्त है -
S → XY, X → a, Y → a | ख
अशक्त निर्माण हटाना
सीएफजी में, एक गैर-टर्मिनल प्रतीक ‘A’ उत्पादन होने पर अशक्त चर है A → ε या एक व्युत्पत्ति है जो शुरू होती है A और अंत में समाप्त होता है
......: A → .......… → ......
निष्कासन प्रक्रिया
Step 1 - अशक्त गैर-टर्मिनल वैरिएबल का पता लगाएं जो able प्राप्त करते हैं।
Step 2 - प्रत्येक उत्पादन के लिए A → a, सभी प्रस्तुतियों का निर्माण A → x कहाँ पे x से प्राप्त किया जाता है ‘a’ चरण 1 से एक या कई गैर-टर्मिनलों को हटाकर।
Step 3 - चरण 2 और निकालने के परिणाम के साथ मूल प्रस्तुतियों को मिलाएं ε - productions।
Problem
निम्नलिखित से शून्य उत्पादन निकालें -
एस → एएसए | aB | बी, ए → बी, बी → बी | ∈
Solution -
दो अशक्त चर हैं - A तथा B
At first, we will remove B → ε.
निकालने के बाद B → ε, उत्पादन सेट बन जाता है -
एस → एएसए | aB | बी | ए, ए, बी | बी | & एप्सिलॉन, बी → बी
Now we will remove A → ε.
निकालने के बाद A → ε, उत्पादन सेट बन जाता है -
एस → एएसए | aB | बी | ए | SA | के रूप में | एस, ए → बी | बी, बी → बी
यह शून्य संक्रमण के बिना अंतिम उत्पादन सेट है।