context free grammar problem

Question

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

Answer 1

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.

Answer 2

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

1. $w = \a^\ell \b v \b^\ell$; or
2. $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).