1
$\begingroup$

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? ?

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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