Context Free Grammar (Peter Linz)

Question

Given the Grammar,

S -> abB,

A -> aaBb,

B -> bbAa,

A -> ∈

Please explain how we get expression:-

L = { ab(bbaa)^n bba (ba)^n / n>= 0 }

Please explain step by step.

Answer 1

smallest string generated by this grammer =

S=>abB

s=>abbbAa

there is two option A->aaBb  or epsilen

put epsilen then smallest string =>abbba

next but A=aaBb

s=>abbbaaBba

again put B=bbAa

​​​​​​​s=>abbbaabbAaba​​​​​​​

there is two option A->aaBb  or epsilen

put epsilen then next string =>ab(bbaa)(bba)(ba)​​​​​​​

put A=aaBb

abbbaabbaaBbaba

put value of B​​​​​​​

abbbaabbaabbAababa

put A=epsilon

ab(bbaabbaa)(bba)(baba)​​​​​​​

you can see that there is a loop between A and B

so we can say

 L = { ab(bbaa)^n bba (ba)^n / n>= 0 }

Comments

Thanks that is nice explanation.

And I am getting

abbb (aabb)^n (ab)^n a /  n>=0

I think it is also correct.

Since we have

abbba

abbb(aabb)(ab)a

abbb(aabb)(aabb)(ab)(ab)a.

ryt?

---

it is also right .