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


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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.