Consider a grammar G with the following production rules: S → SS, S → λ, S → aSb, S → bSa Which one of the following languages is generated using the above rules?

Consider a grammar G with the following production rules: S → SS, S → λ, S → aSb, S → bSa Which one of the following languages is generated using the above rules? Correct Answer L = {w: number of a and b are equal}

The correct answer is option 4.

Concept:

The given grammar is

S → SS,

S → λ,

S → aSb,

S → bSa

The above grammar accepts the strings like, {λ, ab, ba, aabb, abba, bbaa, baab, aaabbb, bbbaaa, ...}

Option 1: L = { anbn:n ≥ 1}

False, The given grammar accepts the strings like {ab, aabb, aaabbb, aaaabbbb, ...} but the strings like {λ, "ba", "abba" , "baab",...} are not accepted by above grammar.

Option 2: L = {w: number of a is > number of b}

False, The given grammar accepts the strings like { a, aa, aab, aba, baa, aaa, aaab, ... } but the strings like {λ, ab, ba } are not accepted by the above grammar.

Option 3: L = { anbn:n ≥ 0}

False,  The given grammar accepts the strings like {λ, ab, aabb, aaabbb, aaaabbbb, ...} but the strings like {λ, "ba", "abba" , "baab",...} are not accepted by above grammar.

Option 4: L = {w: number of a and b are equal}

True, The given grammar accepts the strings like, {λ, ab, ba, aabb, abba, bbaa, baab, aaabbb, bbbaaa, ...}. In every string, the number of a's and number of b's are equal and also even length palindrome. 

Hence the correct answer is L = {w: number of a and b are equal}.