UGC NET Computer Science December 2019 | Question 99

Question 99

---

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:
In options, |-| denotes the cardinality of the set.

1. (1) (K-1) |P| + |T| - 1
2. (2) (K-1) |P| + |T|
3. (3) K |P| + |T| - 1
4. (4) K |P| + |T|

Answer : (2) (K-1) |P| + |T|

Explanation

For any context-free grammar G=(V,T,P,S) without any λ-productions or unit-productions.
The maximum number of production rules are:
(k−1)|P|+|T|
where k is the maximum number of the symbol on the right of production P.

Reference : Prove that there exists an equivalent grammar in Chomsky Normal Form like G′ such that G′ has at most (K−1)|P|+|T| production rules

So, option 2 is correct answer

Previous	Next
UGC NET CS December 2019 - Question 98	UGC NET CS December 2019 - Question 100