Test by Bikram | Mock GATE | Test 3 | Question: 11

Question

Consider the grammar:

• $S\rightarrow$ $PQ | SQ | PS$
• $P\rightarrow k$
• $Q\rightarrow m$

To get a set of $n$ terminals, the number of productions to be used are ______.

• A.     $n^{2}$
• B.     $n + 1$
• C.     $2n - 1$
• D.     $2n$

Comments

This grammar is in Chomsky Normal Form.

Answer 1

By induction, to get a string of length 2 , we need 3 productions

S-->PQ , P->k , Q->m

to get a string of length 3 , we need 5 productions

S --> SQ, S -->  PQ, P -->  k, P -->  m
S => SQ => PQQ => kQQ => kmQ => kmm

Thus we need 2n − 1 productions to get string of length n.

Hence  option C is correct .