MadeEasy WorkBook: Theory of Computation - Context Free Language

Question

CNF may contain the following

(a) null productions

(b) unit productions

(c) useless symbols

(d) all of the above

Given answer is (c)

But in CNF

A-->BC

A-->a

So, answer should be (b), isn't it?

Comments

 

Start symbol may generate null production.

https://www.google.com/amp/s/www.geeksforgeeks.org/converting-context-free-grammar-chomsky-normal-form/amp/

Answer 1

Answer should be option “d” as these can be removed on simplification

Comments

I disagree. Unless you simplify you won’t get CNF. and if option ‘d’ is correct then CNF should have a unit production which means

A → B is a valid production rule in CNF which is definitely not true.

so option ‘b’ and ‘d’ is out of the question.

In CNF S→ null can be there. So there we have option ‘a’