हेल्लो दोस्तों! आज हम इस आर्टिकल में Chomsky’s Normal Form (CNF) in Hindi के बारें में पढेंगे, तो चलिए शुरू करते हैं:-
Chomsky’s Normal Form (CNF) in Hindi
CNF का पूरा नाम Chomsky’s Normal Form है. एक CFG (context free grammar) तब CNF में होता है जब सभी production rules निम्नलिखित conditions को follow करते हैं तो –
- एक non-terminal एक terminal को जनरेट करता है. (उदाहरण के लिए- S →)
- एक non-terminal दो non-terminals को जनरेट करता है. (उदाहरण – S →)
- start symbol जो है वह ε को जनरेट करता है. (उदाहरण – A → ε.)
उदाहरण के लिए
G1 = {S → AB, S → c, A → a, B → b}
G2 = {S → aA, A → a, B → c}
grammar G1 के production rules जो है वे CNF के specify किये हुए rules को संतुष्ट (satisfy) करते हैं, इसलिए grammar G1, CNF में है. परन्तु grammar G2 के production rules, CNF के rules को satisfy नही करते हैं. इसलिए G2, CNF में नही है.
CFG को CNF में convert करने के Steps
step 1 – यदि start symbol (S) दाहिने तरफ (RHS) में है तो एक नया production बनाइए जैसे: S1 → S, जहाँ S1 एक नया start symbol है.
step 2 – grammar में, null, unit और बेकार productions को remove कीजिये.
step 3 – production के RHS से terminals को हटा दें यदि वे अन्य non-terminals या terminals के साथ मौजूद हैं तो। उदाहरण के लिए:- S → aA को निम्नलिखित में तोडा जा सकता है:-
S → RA
R → a
step 4 – दो से अधिक non-terminals के साथ RHS को हटा दें। उदाहरण के लिए:- S → ASB को निम्नलिखित में तोडा जा सकता है.
S → RS
R → AS
निवेदन:- अगर आपके लिए theory of computation (TOC) की यह पोस्ट helpful रही हो तो इसे अपने friends के साथ अवश्य share कीजिये और आपके जो भी questions है आप उन्हें कमेंट करके बता सकते हैं. धन्यवाद.