In formal language theory, a context-free grammar G is said to be in Chomsky normal form if $$ S → A B$$ $$ A → a $$ $$S → ε $$

My question is that if $B$ in the the form of $$ B → abcd $$

where $abcd$ are terminal symbol, is this still in Chomsky Normal Form? ?

  • 1
    $\begingroup$ Wikipedia gives a definition of Chomsky normal form. Next time, I suggest consulting Wikipedia first. $\endgroup$ – Yuval Filmus Aug 8 '17 at 7:35

The above given CFG cannot be in Chomsky Normal Form since the production B→abcd has multiple terminals on left hand side of the production. In order to convert the given CFG to Chomsky Normal Form, will need to replace the terminals on lhs of production B→abcd as follows - B->abcd B->FG F->AE G->CD E->b C->c D->d.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.