# Is $L = \{a^jb^ia^{j-i}\mid i,j \ge 0\ , j > i\}$ context-free?

I'm exercising for an upcoming exam and I find this exercise:

Say whether or not the language $$L = \{a^jb^ia^{j-i}\mid i,j \ge 0\ , j > i\}$$ is a context-free language. Justify your answer.

I have already tried (using the pumping lemma for CFL) with two different words: $$w1 = \ a^pb^{p-1}a$$ $$w2 = \ a^{2p}b^pa^p$$

but I'm stuck when the case is that $vwx$ (considering $uvwxy = w$) take letters from both the first group of $\bf{a}$ and the group of $\bf{b}$.
Have I chosen a wrong format for the word or am I simple missing some trivial condition?

• It may be "even simpler" but note the $j>i$ condition. – Hendrik Jan May 31 '13 at 11:14
• You are right! Damn, it seems that I always dismiss some constraints.. I removed that part. – 5agado May 31 '13 at 13:52

The following grammar shows the contextfreeness $L$:

• $G = (N,T,P,S)$
• $N = \{A, B, S\}$
• $T = \{a, b\}$
• $S = \{S\}$
• $P = \{S \rightarrow aAa, A \rightarrow aAa, A \rightarrow B, B \rightarrow aBb, B \rightarrow \lambda\}$

$L(G) = L$

You are trying the wrong way. It is context-free.

(added.) The structure of the language (to guide the grammar construction) is better seen by setting $k = j-i$, so $j=k+i$. Then the language becomes $\{ a^ka^ib^ia^k \mid i\ge 0, k>0 \}$.

Hint: You can first insert all of the $a$ in stack and then for each $b$ POP one $a$ from stack, then, for each $a$ POP one $a$ from stack.

Because: $i + (j-i)=j$