TIFR CSE 2022 | Part B | Question: 7

Question

Consider the following grammar: $\text{P, Q, R}$ are non-terminals; $c, d$ are terminals; $\text{P}$ is the start symbol; and the production rules follow.

$\mathrm{P}::=\mathrm{QR}$

$\text{Q ::= c}$

$\text{Q} ::=\text{RcR}$

$\text{R ::=ddQ}$

Which of the following is False:

• A. The length of every string produced by the grammar is even
• B. No string produced by the grammar has an odd number of consecutive $d\text{'s}$
• C. No string produced by the grammar has four consecutive $d\text{'s}$
• D. No string produced by the grammar has three consecutive $c\text{'s}$
• E. Every string produced by the grammar has at least has many $d\text{'s}$ as $c\text{'s}$

Answer 1

A)   let find a odd length string

P->QR

P->cR

P->cddQ

P->cddc

OR 

P->RcRR

P->ddQcddQddQ

P->ddccddcddc

no odd string found so it’s even length string True

B) for d’s one production 

R->ddQ 

P->There is no way to produce single d’s, it will be always even

True

C) 

 P→ QR

 P→   RcRR

P→  ddQcRR

P→ ddRcRcRR

P→ddddQcRcRR 

there are 4 consecutive d's

False 

D)

P→ QR

P→ cR

P→ cddQ

P→ cddRcR

P→ cddddQcR

P→ cddddccR

P→ cddddccddQ

P→ cddddccddc

no way to produce 3 consecutive c’s

True

E)

 P-> QR

P-> cR

P->cddQ 

P->cddc 

and as per D option it's proved that d<=c 

True