Teaching UGC NET Mock Test Series 2025 (Paper 1 & 2) Theory of Computation Context Free Languages and Pushdown Automata Context Free Languages
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:
Where |⋅| denotes the cardinality of the set.
1
(K - 1)|P| + |T| -1
2
(K - 1)|P| + |T|
3
K |P| + |T| -1
4
K |P| + |T|