We have to find L(G), where grammar G is given as-
S->AB|CD, A->aA|a ,B->bB|bC, C->cD|d, D->aD|AD
I have attempted the question but it is recursing very deep and I am unable to terminate the string.[I know that A will generate a^n after n steps but what about D,C,B?]
Till now I have attempted as follows-
A->aA->aaA->....->a^(n-1)A (after n-1 steps)->a^n
B->bB->bbB->....->b^(m-1)B (after m-1 steps)->b^(m-1)bC->b^(m-1)bbC->...b^(m-1)b^(n-1)C->b^kC
C->cD->ccD->...->c^(p-1)D or c^(p-1)d[Thus we will consider as C->c^pD or C->c^pd]
D->aD->aaD->...->a^(q-1)D->a^(q-1)a^nD[Thus we will consider D->a^rD]
Now B depends on C and C depends on D and D depends on itself(i.e- D recurs on itself as D->a^rD)
So how can I find the grammar for this language which doesn't terminates?
D does not yield a string of terminals, so it is useless and can be omitted including all rules that has D.
The simplified grammar would be:
S->AB, A->aA|a ,B->bB|bC, C->d
And the language will be: {a^m b^n d : m,n>=1}