Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
This has been flagged as off-topic. Is there a better place for it? – robjohn Apr 24 '13 at 15:54
@robjohn I think 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
up vote 2 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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