Redirected
in Theory of Computation retagged by
1,071 views
0 votes
0 votes

Let $G$ be a grammar in CFG and let $W_1,W_2\in L(G)$ such that $\mid W_1\mid=\mid W_2\mid$ then which of the following statements is true?

  1. Any derivation of $W_1$ has exactly the same number of steps as any derivation of $W_2$.
  2. Different derivation have different length.
  3. Some derivation of $W_1$ may be shorter than the derivation of $W_2$
  4. None of the options
in Theory of Computation retagged by
by
1.1k views

2 Comments

edited by
---
0
0

@lakshman 

could you please correct the answer ?

0
0

1 Answer

1 vote
1 vote
Given data,
W1 and W2 are 2 strings,
|W1|=|W2| means same length
Example CFG grammar:
S→ Cbb | cc
C→ a
W1=cc W2=abb
As per the grammar, W1 require only one derivation S→ cc
W2 requires two derivations S→ Cbb→ abb
It means W1 is smaller than W2.

Correct option- (C) Some derivation of W1 may be shorter the derivation of W2
edited by

2 Comments

edited by
According to Ur explanation:

W1 =  cc

W2= abb

W1 and W2 length is not equal.
I think which grammar u assume is  CFG plz check
0
0
Correct your CFG to

$S \rightarrow Cbb\ |\ ccc$
$C \rightarrow a$
1
1
Answer:

Related questions