TIFR CSE 2020 | Part B | Question: 6

Question

Consider the context-free grammar below ($\epsilon$ denotes the empty string, alphabet is $\{a,b\}$):

$$S\rightarrow \epsilon \mid aSb \mid bSa \mid SS.$$

What language does it generate?

• A. $(ab)^{\ast} + (ba)^{\ast}$
• B. $(abba) {\ast} + (baab)^{\ast}$
• C. $(aabb)^{\ast} + (bbaa)^{\ast}$
• D. Strings of the form $a^{n}b^{n}$ or $b^{n}a^{n},n$ any positive integer
• E. Strings with equal numbers of $a$ and $b$

Comments

The question is revealing the answer. The pdf given by tifr is editable. Just click on tick sign, it will get selected and then you can delete it (i had done it on prev yrs papers on my mac). Removing the bold is bigger problem -- that will probably need paid version of adobe acrobat reader. In case you have that then bold can be removed as well.

 

Other option is manually typing it in Tex.

Answer 1

$S\rightarrow \epsilon \mid aSb \mid bSa \mid SS$

• $S\rightarrow a\underline{S}b$
• $S\rightarrow a\underline{S}Sb$
• $S\rightarrow a a\underline{S}b Sb$
• $S\rightarrow a ab\underline{S}a b Sb$
• $S\rightarrow a aba b \underline{S}b$
• $S\rightarrow a aba b b$

Stings with an equal number of $a's$ and $b's.$

References:

• https://www.cs.wcupa.edu/rkline/fcs/cfls.html#equal-as-bs
• https://stackoverflow.com/questions/55374248/cfg-of-language-which-contains-equal-of-as-and-bs
• https://www.cs.umd.edu/~gasarch/COURSES/250/S15/equal.pdf
• https://courses.engr.illinois.edu/cs373/sp2009/lectures/disc_07.pdf
• https://www.cs.usfca.edu/~galles/cs411/lecture/lecture8.printable.pdf
• https://www.cs.odu.edu/~toida/nerzic/390teched/cfl/cfg.html

So, the correct answer is $(E).$