67 views

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:

1. The length of every string produced by the grammar is even
2. No string produced by the grammar has an odd number of consecutive $d\text{'s}$
3. No string produced by the grammar has four consecutive $d\text{'s}$
4. No string produced by the grammar has three consecutive $c\text{'s}$
5. Every string produced by the grammar has at least has many $d\text{'s}$ as $c\text{'s}$

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

by

1 vote