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

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