UGC NET CSE | December 2014 | Part 2 | Question: 35

Question

The following Context-Free Grammar (CFG) :

$S \rightarrow aB | bA$

$A \rightarrow a | as | bAA$

$B \rightarrow b | bs | aBB$ 

will generate

• A. Odd numbers of $a's$ and odd numbers of $b's$
• B. Even numbers of $a's$ and even numbers of $b's$ 
• C. Equal numbers of $a's$ and $b's$
• D. Different numbers of $a's$ and $b's$ 

Comments

Ans is C equal no of  a and b   in every production  for every a there will be b and vice versa

Answer 1

Answer : A

How answer A is True ?

If you consider this CFG you can definitely generate odd no of a's and odd no of b's no one going to stop you but the real question can you generate all the strings out of this grammar which are having odd no of a's and odd no of b's Answer is no you can't generate.

Consider option B : The string in which you have abbb (odd no of a's and odd no of b's ).This string can't be generate by this grammar you can try it .We only consider the Language if it is able to generate all the possible strings of that type .

Consider the option C : here again you can generate the strings having odd no of a's and even no of b's but you can't generate all .One of the string which you can't generate is " a" (Here we have 1-a and 0 no of b's) .

consider the option D  :here again we are able to generate some of the string which are having even no of a's and even no of b's .But not all Here is the Exp : we can't generate epsilon in which we have even no of a's and even no of b's .

Finally Consider option A in this you can generate all possible string out of this grammar in which you are going to have equal no of a's and equal no of b's .

That's why option A is correct .

Comments

yes, option A is correct.

since after generating all sets of string it gives equal no of a's & b's.

Answer 2

Option A) would be the correct answer.

Because we can generate the string aabb (Which is a contradiction to Option B and C).

Given CFL also can generate ab (Which is contradiction to the option D). 

Comments

your ans does not make any sense because have not  explained it properly .

as you said it is generating aabb how it is contradiction to B and C  .if you are generating  aabb option c does not stop you to generate odd no of a's and odd no of b's . this is the string which can be generated by this ab in which we have odd no of a's and odd no of b's .

we can also generate odd no of a's and even no of b's and similarly even number of a's and even number of b's.

we can generate all the string which are given in the options.

---

I tell u if u generate odd no of a's u must also take the load to generate the same no. of b's. The rules will force you to if u want to end the productions to a 'string' as each additional 'a' will come with luggage as aBB. Same is true for reverse i.e.odd b's & same if we reverse odd with even & v.v.

 

A) is correct.

Answer 3

Refer this for Solution

Answer 4

Answer C: Equal number of a's and b's

Option A is false because we can get even number of a's and even number of b's.

Example1: S -> bA -> bbAA -> bbaA -> bbaa

option B is false because we can get odd number of a's and odd number of b's.

Example2: S -> aB -> ab

The above two examples are creating equal number of a's and b's. This makes option D false

Comments

please explain your answer in detail.

give reasons why other options are incorrect.