Let G=(V, T, S, P) be any context-free grammar λ without any -productions or unit productions. Let K be the maximum number of symbols on the right of any production in P. The maximum number of production rules for any equivalent grammar in Chomsky normal form is given by: 1 − I Where denotes the cardinality of the set.

1. A(K − 1)|P| + |T| − 1
2. B(K − 1)|P| + |T|
3. CK|P| + |T| − 1
4. DK|P| + |T|

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. (K − 1)|P| + |T|

Explanation

Each production with K symbols on the right splits into at most K − 1 binary rules, and one rule per terminal (A_t → t) is added: (K − 1)|P| + |T|.