चॉम्स्की सामान्य रूप

यदि प्रोडक्शंस निम्नलिखित रूपों में हैं तो एक सीएफजी चॉम्स्की नॉर्मल फॉर्म में है -

• ए → ए
• A → ई.पू.
• एस → ε

जहाँ A, B, और C गैर-टर्मिनल हैं और a टर्मिनल है।

एल्गोरिदम को चॉम्स्की सामान्य रूप में परिवर्तित करने के लिए -

Step 1 - अगर स्टार्ट सिंबल S कुछ दाईं ओर होता है, एक नया प्रारंभ प्रतीक बनाएँ S’ और एक नया उत्पादन S’→ S।

Step 2- अशक्त प्रस्तुतियों को हटा दें। (पहले चर्चा की गई नल उत्पादन हटाने एल्गोरिथ्म का उपयोग)

Step 3- यूनिट प्रोडक्शंस निकालें। (यूनिट उत्पादन हटाने एल्गोरिथ्म का उपयोग पहले चर्चा की)

Step 4 - प्रत्येक उत्पादन बदलें A → B₁…B_n कहाँ पे n > 2 साथ में A → B₁C कहाँ पे C → B₂ …B_n। दाईं ओर दो या दो से अधिक प्रतीकों वाली सभी प्रस्तुतियों के लिए इस चरण को दोहराएं।

Step 5 - यदि किसी भी उत्पादन का सही पक्ष फॉर्म में है A → aB जहां एक टर्मिनल है और A, B गैर-टर्मिनल हैं, फिर उत्पादन द्वारा प्रतिस्थापित किया जाता है A → XB तथा X → a। प्रत्येक उत्पादन के लिए इस चरण को दोहराएं जो फॉर्म में हैA → aB।

मुसीबत

निम्नलिखित CFG को CNF में परिवर्तित करें

एस → एएसए | ए बी, ए → बी | एस, बी → बी | ε

समाधान

(1) जबसे S RHS में प्रकट होता है, हम एक नया राज्य जोड़ते हैं S₀ तथा S₀→S उत्पादन सेट में जोड़ा जाता है और यह बन जाता है -

एस ₀ → एस, एस → एएसए | ए बी, ए → बी | एस, बी → बी | ∈

(2) अब हम अशक्त प्रस्तुतियों को हटा देंगे -

बी → A और ए → A

बी → ε को हटाने के बाद, उत्पादन सेट बन जाता है -

एस ₀ → एस, एस → एएसए | aB | ए, ए → बी | एस | B, बी → बी

A → ∈ को हटाने के बाद, उत्पादन सेट बन जाता है -

एस ₀ → एस, एस → एएसए | aB | ए | के रूप में | SA | एस, ए → बी | एस, बी → बी

(3) अब हम यूनिट प्रोडक्शंस को हटा देंगे।

S → S को हटाने के बाद, उत्पादन सेट बन जाता है -

एस ₀ → एस, एस → एएसए | aB | ए | के रूप में | एसए, ए → बी | एस, बी → बी

S ₀ → S को हटाने के बाद , उत्पादन सेट बन जाता है -

एस ₀ → एएसए | aB | ए | के रूप में | एसए, एस → एएसए | aB | ए | के रूप में | एसए

A → बी | एस, बी → बी

A → B निकालने के बाद, उत्पादन सेट बन जाता है -

एस ₀ → एएसए | aB | ए | के रूप में | एसए, एस → एएसए | aB | ए | के रूप में | एसए

ए → एस | ख

बी → बी

ए → एस को हटाने के बाद, उत्पादन सेट बन जाता है -

एस ₀ → एएसए | aB | ए | के रूप में | एसए, एस → एएसए | aB | ए | के रूप में | एसए

A → b | ASA | aB | ए | के रूप में | एसए, बी → बी

(4) अब हम RHS में दो से अधिक वेरिएबल्स का पता लगाएंगे

यहाँ, S ₀ → ASA, S → ASA, A → ASA RHS में दो गैर-टर्मिनलों का उल्लंघन करता है

इसलिए हम निम्नलिखित अंतिम उत्पादन सेट प्राप्त करने के लिए चरण 4 और चरण 5 लागू करेंगे जो कि CNF में है -

एस ₀ → एएक्स | aB | ए | के रूप में | एसए

S → AX | aB | ए | के रूप में | एसए

A → b | AX | aB | ए | के रूप में | एसए

बी → बी

एक्स → एसए

(5)हमें प्रोडक्शंस एस ₀ → ए बी, एस → ए बी, ए → ए बी को बदलना होगा

और अंतिम उत्पादन सेट बन जाता है -

एस ₀ → एएक्स | YB | ए | के रूप में | एसए

S → AX | YB | ए | के रूप में | एसए

A → b A → b | AX | YB | ए | के रूप में | एसए

बी → बी

एक्स → एसए

Y → a