Michael Sipser Edition 3 Exercise 2 Question 19 (Page No. 156)

Question

Let $CFG$   $G$ be the following grammar$.$

•  $S\rightarrow aSb \mid bY \mid Y a$
• $Y\rightarrow bY \mid aY \mid \epsilon$

Give a simple description of $L(G)$ in English$.$ Use that description to give a $CFG$ for $\overline{L(G)},$ the complement of $L(G).$

Comments

L(G)=$a^nxb^n$ | $x\epsilon (a|b)^+$