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

Question

Which of the regular expressions corresponds to this grammar ?

$S → AB/AS, A → a/aA, B → b$

• A. $aa^*b^+$

• B. $aa^*b$

• C. $(ab)^*$

• D. $a(ab)^*$

Answer 1

S->AB|AS,  A->a/aA,  B->b (b will appear exactly  once so option A,C, D are out)

S->AB->ab (smallest string )

or

S->AB->aAb->aaAb...   and so on  aa*b

or S->AS->AAS->AAAS.... so on  aa*b

option B is the ans

Comments

why not A?

---

as mentioned  option A  will contain any number of b (1,2,3,.)  , while given grammar can produce only one b