-
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 is not generated by G ?
-
- abab
- aaab
- abbaa
- babba
- abab
Correct Option: D
The given grammar with productions,
S → SaS | aSb | bSa | SS | ∈
Now consider,
S → aSb | bSa | SS | ∈
This grammar generates all strings with equal number of ‘a’ and ‘b’.
Now, S → SaS can only generate strings where ‘a’ is more than ‘b’. Since on left and right of ‘a’ in SaS, S will have only strings with na = nb or na > nb.
Now consider each options
1. S → SS → aSbS → abS → abaSb → abab ,when, S → ∈
2. S → aSb → aSaSb → aaaSb → aaab , when S → ∈
3. S → SS → aSbS → abS → abbSa → abbSaSa → abbaa, when ( S → ∈ )
4. “babba” which is a string with nb > na is not possible to generate by the given grammar.
Hence, option (d) is correct.
