Problem Detail: $L = { a^ib^j mid jneq i and jneq2i } $ Is this language a context free language? If yes give a PDA. If no, give a proof. The pumping lemma for context free languages doesn’t seem to work here. Let $p>1$ be the pumping length. Let the string be divided into five parts according to pumping lemma as $w = uvxyz$. For any string of the form $a^ib^j s.t.$:
- $ jlt i-1$ choose $v=a, x=epsilon, y=epsilon$
- $ jgt 2i+1$ choose $v=epsilon, x=epsilon, y=b$
- $ j = i-1$ choose $v=a, x=epsilon, y=b$
- $ j = 2i+1$ choose $v=a, x=epsilon, y=b$
- $ jgt i, jlt 2i $ choose $v=a, x=epsilon, y=b$
Asked By : emmy
Answered By : Ran G.
It is context Free. You can see it as a union of two languages: $L_1$ where $j>2i$ and $L_2$ which is very similar to the one of this question. More information you can find in this question.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10635
