recategorized by
486 views
1 votes
1 votes

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}$
recategorized by

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

0 votes
0 votes
1 answer
1
3 votes
3 votes
1 answer
2
admin asked Sep 1, 2022
531 views
Which data structure is commonly used to implement breadth first search in a graph?A queueA stackA heapA hash tableA splay tree
4 votes
4 votes
2 answers
3
1 votes
1 votes
1 answer
4
admin asked Sep 1, 2022
800 views
Consider the problem of sorting $n$ single digit integers (base $10$). This problem can be solved in time$O(n \log n)$ but not $O(n \log \log n)$$O(n \log \log n)$ but no...