13 views

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).$

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