Chomsky normal form and Greibach normal form in hindi

Unit 3

Grammars

Topic 6 : Chomsky normal form and Greibach normal form in hindi

Chomsky normal form :

formal language theory में, एक context-free grammar, G, को Chomsky normal form में कहा जाता है यदि इसके सभी production rules form के हैं :

A → BC, or

A → a, or

S → ε,

जहाँ A, B, और C nonterminal symbols हैं, letter a एक terminal symbol (एक symbol जो एक constant value को represents करता है), S start symbol है, और ε empty string को दर्शाता है। इसके अलावा, न तो B और न ही C start symbol हो सकता है, और third production rule केवल तभी appear हो सकता है |

Chomsky normal form में प्रत्येक grammar context-free है, और इसके conversely , प्रत्येक context-free grammar को एक equivalent में बदला जा सकता है, जो Chomsky normal form में है और इसकी original grammar के आकार के square से बड़ा नहीं है।

Greibach normal form :

GNF इसे Greibach normal form भी कहा जाता है । एक CFG (context free grammar) GNF (Greibach normal form) में है यदि सभी production rules निम्न में से किसी एक कारण को पूरा करते हैं :

एक start symbol generating ε । उदाहरण के लिए, S → ε।
एक non-terminal एक terminal generate करता है। उदाहरण के लिए, A → a.
एक non-terminal एक terminal generate करता है जो किसी भी number में non-terminal follow किया जाता है। उदाहरण के लिए, S → aASB

For example:

G1 = {S → aAB | aB, A → aA| a, B → bB | b}
G2 = {S → aAB | aB, A → aA | ε, B → bB | ε}

NP Complete Problem in Hindi

NP-Complete problems एक महत्वपूर्ण वर्ग हैं जो computational complexity the...

Multihead Turing Machine और Multidimensional Turing Machine की विशेषताएँ और अंतर

Multihead Turing Machine एक प्रकार की Turing Machine है जिसमें एक से अ�...

Universal Turing Machine and Multitape in Hindi

Universal Turing Machine (UTM) एक ऐसी ट्यूरिंग मशीन है, जो किसी भ...

Techniques for Turing Machine Construction in Hindi

Turing Machine कंप्यूटर विज्ञान में एक theoretical model है, जो क�...

Petri Net Model in Hindi | Theory of Computation (TOC) Explained

Petri Net एक mathematical model है जो systems के behavior को graphically represent करने �...

Chomsky normal form and Greibach normal form in hindi