हेल्लो दोस्तों! आज हम इस आर्टिकल में 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
Summary (सारांश)
Chomsky's Normal Form (CNF) in Hindi - TOC के इस आर्टिकल में सीखेंगे कि CNF क्या होता है और कैसे एक Context Free Grammar (CFG) को CNF में बदला जाता है। इसमें CNF की तीन मुख्य conditions को उदाहरणों के साथ समझाया गया है, जैसे कि एक non-terminal को terminal या दो non-terminals में बदलना। साथ ही, CFG को CNF में convert करने के चार steps को आसान भाषा में समझाया गया है, जिसमें null, unit और useless productions को हटाना, terminals को अलग करना, और RHS में दो से अधिक non-terminals को तोड़ना शामिल है। - क्या मिलेगा: CNF की परिभाषा, उदाहरण, और conversion process के चरण। - क्या सीखेंगे: छात्र CNF की शर्तों को पहचानना और किसी भी CFG को CNF में बदलना सीखेंगे। - Exam preparation में मदद: TOC के numerical questions और proofs को हल करने में यह article बहुत उपयोगी है, क्योंकि CNF से जुड़े सवाल अक्सर परीक्षा में पूछे जाते हैं।
निवेदन:- अगर आपके लिए theory of computation (TOC) की यह पोस्ट helpful रही हो तो इसे अपने friends के साथ अवश्य share कीजिये और आपके जो भी questions है आप उन्हें कमेंट करके बता सकते हैं. धन्यवाद.