Unknown Chomsky normal form and Greibach normal form in hindi | My Project HD | My Project HD
X

Chomsky normal form and Greibach normal form in hindi

Computer Science Engineering Tutorials in Hindi | Theory of Computation

Chomsky normal form and Greibach normal form in hindi

Computer Science Engineering Tutorials in Hindi | Theory of Computation



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  निम्न में से किसी एक कारण को पूरा करते हैं :

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

For example:

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


More Tutorials

Web Technology Tutorials in Hindi

Web Technology Tutorials in Hindi

Read More
Diploma engineering tutorial for polytechnic collage

Diploma Engineering Tutorial

Read More
Final Year Projects for Computer Science with Source Code

Final Year Projects for Computer Science with Source Code

Read More