[Solved]: Is $L = {a^jb^ia^{j-i}mid i,j ge 0 , j > i}$ context-free?

ignougroup
Problem Detail: 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?

Asked By : 5agado

Answered By : Odin

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$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12370  Ask a Question  Download Related Notes/Documents