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 | ε}