Proving language is context-free with pumping lemma

Question

I've got a test coming up in using the pumping lemma to prove whether or not a language is context free. I'm trying to work through some practice problems and things aren't going so great...

The practice problem is: For a) through j), prove whether or not the following language is context free or not. If it is context-free, give a context-free grammar that generates it.

The first two are:

a) {a^(2i+1) b^(3k+2) c^(4k+3) d^(5i+4) | i >= 0, k >= 0}

b) {a^i b^i c^k d^i | i >= 1, k >= 1}

If someone can solve these first two, giving a detailed explanation of how they did it, I'm sure I'll be able to figure out the rest (c through j) on my own.

Answer 1

a is context free:

A -> aBdddd
B -> aaBddddd
B -> C
C -> bbbCcccc
C -> D
D -> bbccc

B is not context free. Let's assume it is. We therefore have an integer p for which the pumping lemma holds. Let's look at the following word in b: a^p b^p c d^p

According to the pumping lemma, this word can be represented as the sequence uvwxy, such that |vwx| < p, and u v^i w x^i y is also in B.

let's look at vx:

Case 1: vx contains "c". If that's the case, then uwy is supposed to also be in B, but B requires that we have at least one "c". So that case is impossible.

Case 2: vx doesn't contain "c". It must contain at most two of "a", "b" or "c" (or else |vwx| would be more than p). Therefore, uv^2wx^2y will not contain an equal number of a, b and c, and is also not in B.

B is, therefore, not a context free language.