If G is a grammar with productions S → SaS | aSb | bSa | SS | ∈ Where S is the start variable. Then which one of the following strings in not generated by G?

If G is a grammar with productions S → SaS | aSb | bSa | SS | ∈ Where S is the start variable. Then which one of the following strings in not generated by G? Correct Answer babba

STEP:

Consider all the strings, then check if they can be generated from given grammar or not.

Derivation:

Grammar Production: S → SaS | aSb | bSa | SS | ∈

Option 1: String: abab

S → aSb

S → abSab 

S → ab∈ab

S → abab

So, abab can be generated by the given grammar.

Option 2: String: aaab

S → SS

S → SaSS 

S → SaSaSS 

S → aaaSbS 

S → aaa∈bS 

S → aaa∈b∈ 

S → aaab

Option 3: String:  abbaa

S → SS

S → aSbS 

S → a∈bS 

S → abbSa  

S → abbSaSa 

S → abb∈aSa

S → abba∈a

S → abbaa  

All three abab, aaab and abbaa are generated by the given grammar.