UGC NET CSE | June 2006 | Part 2 | Question: 1

Question

Which of the following strings is in the language defined by grammar $S\rightarrow OA,$ $A\rightarrow1A/0A/1$

• A. $01100$
• B. $00101$
• C. $10011$
• D. $11111$

Answer 1

There seems to be a mistake in the grammar given.

Assuming the grammar is $S\rightarrow0A,A\rightarrow1A/0A/1$,

The grammar generates strings which start with 0 and end with 1.

So only option b is the answer.

OR

$S\rightarrow0A$

$S\rightarrow00A$

$S\rightarrow001A$

$S\rightarrow0010A$

$S\rightarrow00101$

Hence option B is answer