context-free-grammarleft-recursionchomsky-normal-form

Does Chomsky Normal Form have left recursion?

one of famous form of CFG is CNF and as you know its have two non terminal as its RHS or one terminal as its RHS and empty RHS,if exists, appear only in RHS of root as described in this Wiki , but I'm not sure does CNF allow us to have left recursion?

Solution

  • Yes, CNF allows any form of recursion.