in Compiler Design recategorized by
80 views
1 vote
1 vote

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}$
in Compiler Design recategorized by
by
80 views

1 Answer

0 votes
0 votes

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

 

 

 

 

edited by
Answer:

Related questions