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?

  • 1
    $\begingroup$ It may be "even simpler" but note the $j>i$ condition. $\endgroup$ – Hendrik Jan May 31 '13 at 11:14
  • $\begingroup$ You are right! Damn, it seems that I always dismiss some constraints.. I removed that part. $\endgroup$ – 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$


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.