context free grammar problem $L$ is the context free grammar over $\{a, b\}$
$S \rightarrow aSb \; | \;bR \; |\;Ra$
$R \rightarrow bR \;|\;aR\;|\;\epsilon$
Briefly describe this CFG with English sentences and prove your description. Then give a CFG for the complement of $L$.  
$\\$
I think the CFG is a language with equal amount of $a$ at the beginning and $b$ in the end, in the middle with a string that consists of $a$ and $b$, and either starts with $b$ or ends with $a$. But I'm not sure if it's correct nor do I know how to formally prove my description. 
For the complement, I'm not sure how to design the CFG. 
Is anyone able to solve this problem? Thanks.
 A: You noted that the language generated by $\newcommand{\a}{\mathtt{a}}\newcommand{\b}{\mathtt{b}}L$ appears to be exactly the collection of all strings of the following two forms


*

*$w = \a^\ell \b v \b^\ell$; or

*$w = \a^\ell v \a \b^\ell$


for some string $v \in \{ \a , \b \}^*$.
To prove that the CFG generates exactly these strings we'll just demonstrate that every such string can be generated by $L$, and every string generated by $L$ is of one of those two forms.  (This will be pretty hand-wavy, but the ideas can be made formal.)

If $w = \a^\ell \b v \b^\ell$, then after applying the rule $S \rightarrow \a S \b$ $\ell$ times we have $\a^\ell S \b^\ell$.  From here apply the rule $S \rightarrow \b R$ to get $\a^\ell \b R \b^\ell$ and it is straightforward to show that the "sub-CFG" consisting of only the $R$-rules can generate every string over $\{ \a , \b \}$.
  If $w = \a^\ell v \a \b^\ell$ we procede similarly, but take the rule $S \rightarrow R \a$ at the appropriate point.
To show that every string generated by $L$ is of one of the above forms, note that any generation must apply the rule $S \rightarrow \a S \b$ $\ell$ many times (for some $\ell \geq 0$), yielding $\a^\ell S \b^\ell$, and then apply either the rule $S \rightarrow \b R$ or $\mathtt{S} \rightarrow R \a$, yielding $\a^\ell \b R \b^\ell$, $\a^\ell R \a \b^\ell$, respectively.  From here we use the $R$ rules to generate some sub-string $v$ resulting in either $\a^\ell \b v \b^\ell$, $\a^\ell v \a \b^\ell$.

To design a CFG for the complement of the language above, I'll just leave a hint:

Hint: For every string $w \in \{ \a , \b \}^*$ there is a largest integer $\ell \geq 0$ such that $w = \a^\ell v \b^\ell$ for some string $v$.  Note that $v$ cannot be of the form $\a u \b$ for some substring $u$ (since $\ell$ was taken to be largest possible).  But then what possible forms can $v$ take?  And which of these possibilities cannot be generated by $L$, above?

Correct answers to the questions in the hint should result in a simpler description of the language generated by $L$ (since there is actually a pretty simple description of the complement).
A: Let $A = \{a,b\}$. Then the language $L$ is the least solution in $S$ of the system of equations
\begin{align}
S &= aSb + bR + Ra \\
R &= bR + aR + 1
\end{align}
where $+$ denotes union and $1$ denotes the empty word. The second equation gives $R = (a+b)R + 1 = AR + 1$ and has $R = A^*$ as unique solution. Reporting in the first equation yields $S = aSb + bA^* + A^*a$. Setting $K = bA^* + A^*a$, it can be written as $S = aSb + K$, which leads the solution
$$
  L = \{ a^nub^n \mid n \geqslant 0 \text{ and } u \in K \}
$$
For the second part, I have nothing to add to the excellent suggestion of Arthur Fischer.
