Peter Linz Edition 4 Exercise 1.2 Question 14.g (Page No. 29)

Question

$L = \left \{ a^{n} b^{m} : n\geq 0,m>n \right \}$

Find a grammar that generates $L^3$

Comments

$S \rightarrow AbAbAb $

$A \rightarrow aAb| Ab | \epsilon $

Answer 1

$L^3 = \{a^pb^qa^rb^sa^tb^u|p,r,t\geq 0, q >p, s>r, u>t \}$

Grammar for this language:

$S \rightarrow AAA$

$A \rightarrow aAb\ |\ B$

$B \rightarrow bB\ |\ b$

P.S. If you take $A$ as the starting symbol, then you get the language $L$.