recategorized by
2,010 views
1 votes
1 votes

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
recategorized by

3 Answers

1 votes
1 votes

option A is the correct answer

1 votes
1 votes

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
0 votes
0 votes
Language generated is: a there must be b.

So B,C and D are wrong.

So A is correct.
Answer:

Related questions

1 votes
1 votes
3 answers
1
Arjun asked Dec 7, 2018
1,179 views
The language $\{ W^a X^b Y^{a+b} \mid a, b, >1\}$ isRegularContext-free but not regularContext sensitive but not context freeType$=0$ but not context sensitive
0 votes
0 votes
4 answers
2
Arjun asked Dec 7, 2018
2,608 views
Identify the total number of tokens in the given statementprintf("A%B=",&i);$7$$8$$9$$13$
0 votes
0 votes
2 answers
3
Arjun asked Dec 7, 2018
2,176 views
Among all given option, ____ must reside in the main memory.AssemblerCompilerLinkerLoader
1 votes
1 votes
2 answers
4
Arjun asked Dec 7, 2018
4,346 views
Which of the following code replacements is an example of operator strength reduction?Replace $ \text{P^2} $ by $P^*P$Replace $ P^*16$ by $P<<4$Replace $ \text{pow}(P,3) ...