# How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j a^k| j \gt i+k\}$?

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j a^k| j \gt i+k\}$?

My attempt:

$G_1 = (\{ S,A,B\}, \{a,b\},P,S)$ where $P$ consists of: $$S\to AbBC$$ $$A \to aAb|\lambda$$ $$B \to bB|\lambda$$ $$C \to bCa|\lambda$$

Is this correct?

-
This has been flagged as off-topic. Is there a better place for it? – robjohn Apr 24 '13 at 15:54
@robjohn I think cs.stackexchange.com would be a much better fit. – haunted85 Apr 24 '13 at 15:59
@haunted85 The same user asked (almost) the same question on Computer Science earlier this day and deleted it again. Not clear whether the reason was self-vandalism, sulkiness or something else entirely. – Raphael Apr 24 '13 at 17:27
@haunted85: We routinely answer such questions. – Brian M. Scott Apr 24 '13 at 21:05
This is a special case of this recent question; the accepted answer there, combined with Arthur Fischer’s answer, should help. – Brian M. Scott Apr 24 '13 at 21:06

## 1 Answer

The strings your grammar generate are of the form $\mathtt{a}^i \mathtt{b}^{j} \mathtt{a}^k \mathtt{b}^k$ (or $\mathtt{0}^i \mathtt{1}^{j} \mathtt{0}^k \mathtt{1}^k$ with notational changes) where $j > i$. (You're use of the non-terminal $A$ in two spots in the starting rule made you go awry as the order of the $\mathtt{a}$s and $\mathtt{b}$s (or $\mathtt{0}$s and $\mathtt{1}$s) matters.)

Don't be afraid to use more non-terminal symbols! (well, one more.)

-