in Compiler Design recategorized by
1,995 views
1 vote
1 vote

The context free grammar $S \rightarrow aSb \mid bSa \mid \epsilon$ generates:

  1. Equal number of a’s and b’s
  2. Unequal number of a’s and b’s
  3. Any number of a’s followed by any number of b’s
  4. Any number of b’s followed by any number of a’s
in Compiler Design recategorized by
by
2.0k views

3 Answers

1 vote
1 vote

option A is the correct answer

2 Comments

Wrong. Option A is incorrect as well.
2
2

Yes right option A is incorrect  because some of the strings like abba can’t be generated by the given grammar 

0
0
1 vote
1 vote

All the options are wrong. B, C and D can be easily ruled out, so let's focus on option (a) now.

As far as option (a) is concerned, it turns out that, even (a) is not the correct answer. How? It is because the grammar cannot generate all the strings having equal number of $a$'s and $b$'s. For example, $abba$ is one such string which cannot be generated by the above grammar. Then what is the best way to describe the above grammar? It generates strings having equal number of a's and b's provided that, the string starts and ends with different symbols i.e. Starting with $a$ and ending with $b$, or starting with $b$ and ending with $a$. So the conclusion is, all options are wrong.

Note: Even though A is wrong, in an exam scenario it will be the most appropriate option to mark as correct. So from an exam point of view, A may be marked in the OMR sheet, but from a conceptual standpoint, A is wrong.

edited by

3 Comments

I agree with you but if we think about closest option only A turns out to be the answer and it did. In official key they mentioned A as the answer.

So in order to avoid the marks unnecessarily going with closest one can save us. If the exam conducting authority drops such question in evaluation its good but IF THEY DON'T it can harm us vigorously.
0
0
edited by
Yes, you'll obviously do that during the exam, but people here are coming to understand the actual concept. So saying that A is correct just because others are wrong is not good and can mislead people into believing that A is the right grammar, when it clearly isn't. Still I will add this as a side note to my answer that it is most appropriate to mark A as correct in the exam scenario.
1
1
I appreciate your concern👍
0
0
0 votes
0 votes
Language generated is: a there must be b.

So B,C and D are wrong.

So A is correct.

1 comment

Even though B, C and D are wrong, that still doesn't make option A correct. Refer my answer to get more insight on this.
0
0