Register

NIELIT 2017 DEC Scientist B - Section B: 7

• retagged by
1,114 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
• retagged by
User Avatar

1 Answer

1 votes
1 votes
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
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
admin asked Mar 30, 2020
1,248 views
NIELIT 2017 DEC Scientist B - Section B: 26
The grammar $S\rightarrow aSb\mid bSa\mid SS\mid \varepsilon $ is: Unambiguous CFG Ambiguous CFG Not a CFG Deterministic CFG
The grammar $S\rightarrow aSb\mid bSa\mid SS\mid \varepsilon $ is:Unambiguous CFGAmbiguous CFGNot a CFGDeterministic CFG
User Avatar
0 votes
0 votes
6 answers
2
admin asked Mar 30, 2020
2,452 views
NIELIT 2017 DEC Scientist B - Section B: 2
According to the given language, which among the following expressions does it correspond to ? Language $L=\{x\in\{0,1\}\mid x\text{ is of length 4 or less}\}$. $(0+1+0+1+0+1+0+1)^4$ $(0+1)^4$ $(01)^4$ $(0+1+\varepsilon)^4$
According to the given language, which among the following expressions does it correspond to ?Language $L=\{x\in\{0,1\}\mid x\text{ is of length 4 or less}\}$.$(0+1+0+1+0...
User Avatar
1 votes
1 votes
3 answers
3
admin asked Mar 30, 2020
2,067 views
NIELIT 2017 DEC Scientist B - Section B: 10
A regular expression is $(a+b^{\ast}c)$ is equivalent to set of strings with either $a$ or one or more occurrence of $b$ followed by $c$. $(b^{\ast}c+a)$ set of strings with either $a$ or zero or more occurrence of $b$ followed by $c$. Both (B) and (C)
A regular expression is $(a+b^{\ast}c)$ is equivalent toset of strings with either $a$ or one or more occurrence of $b$ followed by $c$.$(b^{\ast}c+a)$set of strings with...
User Avatar
Link Copied!