ग्रीबाच सामान्य रूप
यदि प्रोडक्शंस निम्नलिखित रूपों में हैं तो एक सीएफजी ग्रीबाच नॉर्मल फॉर्म में है -
ए → बी
A → bD 1 ... D n
एस → ε
जहाँ A, D 1 , ...., D n गैर-टर्मिनल हैं और b एक टर्मिनल है।
एक CFG को ग्रीबच नॉर्मल फॉर्म में बदलने के लिए एल्गोरिदम
Step 1 - अगर स्टार्ट सिंबल S कुछ दाईं ओर होता है, एक नया प्रारंभ प्रतीक बनाएँ S’ और एक नया उत्पादन S’ → S।
Step 2- अशक्त प्रस्तुतियों को हटा दें। (पहले चर्चा की गई नल उत्पादन हटाने एल्गोरिथ्म का उपयोग करना)
Step 3- यूनिट प्रोडक्शंस निकालें। (यूनिट उत्पादन हटाने एल्गोरिथ्म का उपयोग पहले चर्चा की)
Step 4 - सभी प्रत्यक्ष और अप्रत्यक्ष वाम-पुनरावृत्ति को हटा दें।
Step 5 - इसे GNF के उचित रूप में परिवर्तित करने के लिए प्रस्तुतियों का उचित प्रतिस्थापन करें।
मुसीबत
निम्नलिखित CFG को CNF में परिवर्तित करें
S → XY | Xn | पी
एक्स → एमएक्स | म
Y → Xn | हे
उपाय
यहाँ, Sकिसी भी उत्पादन के दाईं ओर दिखाई नहीं देता है और उत्पादन नियम सेट में कोई इकाई या अशक्त प्रोडक्शंस नहीं हैं। तो, हम चरण 1 को चरण 3 पर छोड़ सकते हैं।
Step 4
अब बदलने के बाद
X इन S → XY | Xo | पी
साथ में
एमएक्स | म
हमने प्राप्त किया
एस → एमएक्सवाई | एमवाय | mXo | मो | पी
और बदलने के बाद
X in Y → X n | हे
के दाईं ओर
एक्स → एमएक्स | म
हमने प्राप्त किया
Y → mXn | एमएन | ओ
दो नए निर्माण O → o और P → p को उत्पादन सेट में जोड़ा जाता है और फिर हम निम्नलिखित के रूप में अंतिम GNF में आए -
एस → एमएक्सवाई | एमवाय | एमएक्ससी | mC | पी
एक्स → एमएक्स | म
Y → mXD | mD | हे
ओ → ओ
पी → पी