UGC NET CSE | June 2012 | Part 3 | Question: 39

Question

The following CFG $S \rightarrow aB \mid bA, A \rightarrow a \mid as \mid bAA, B \rightarrow b \mid bs \mid aBB$ generates strings of terminals that have

• A. odd number of a’s and odd number of b’s
• B. even number of a’s and even number of b’s
• C. equal number of a’s and b’s
• D. not equal number of a’s and b’s

Answer 1

Refer to this Answer for explanation : CFL

Answer 2

eliminate one by one

for D :S-->aB-->ab (GENERATES #a  = #b) SO IT IS WRONG

FOR A:  CONSIDER THE STRING aaab (ODD NUM OF a'S AND ODD NUM OF b'S)

            S-->aB-->aaBB-->aaaBBB-->aaabbb  ( WE ARE NOT ABLE TO GET)

FOR B:  CONSIDER THE STRING  aaaabb ( EVEN NUM OF a'S AND EVEN NUM OF b'S)

           S-->aB-->aaBB-->aaaBBB-->aaaaBBBB-->aaaabbbb(WE ARE NOT ABLE TO GET)

SO A,B,D ARE WRONG

NOW LOOK AT THE OUTPUTS OF A,B,D ..THESE ARE:  ab,aaabbb,aaaabbbb

which shows we can get #a's  =  # b's

so C is the ans