What strings are generated by this grammar?
S --> aB        S --> bA
B --> b         A --> a
B --> bS        A --> aS
B --> aBB       A --> bAA


what strings is generated by the grammar?

Shraddha @shraddhagami
8 Feb 2017 05:19 pm

No. Of a's is equal to no. Of b's

By tracing we get set of strings derived from a grammar

skkarpe @sharmilakarpe
8 Feb 2017 05:32 pm


Shraddha @shraddhagami
8 Feb 2017 05:55 pm


We can't generate abb from given grammar

karmjit joshi @karmjitjoshi
8 Feb 2017 06:17 pm

plz explain how to solve this?

@shraddhagami nd @sharmilakarpe

Sumit Verma @sumitkgp
8 Feb 2017 06:21 pm

@karmjitjoshi To solve such problems, try to derive some strings from the given grammar.

karmjit joshi @karmjitjoshi
8 Feb 2017 06:26 pm

how? sir

Sumit Verma @sumitkgp
8 Feb 2017 06:46 pm


It is clear that string can start from either a or b from these two productions
S --> aB, S --> bA .
Now let's take a string that will start from a.
So we will use production, S --> aB.
We have three choices for B as B -->b, B --> bS, B --> aBB
If we use B -->b , our string will be ab.
If we use B --> bS, we will get abS // Now you can again start with either a or b.
If we use B --> aBB, we will get aaBB. // Now you have again three options for every B.
But, In every case you have equal count of  of a and b.
Similary, you can check for the strings starting from b as well.

karmjit joshi @karmjitjoshi
8 Feb 2017 07:28 pm

thanks a lot @sumitverma sir for this wonderful explanation