Ogden's lemma : If L is a CFL, then there is a constant n, suchthat if z is any string of length at least n in L, in which weselect at least n positions to be distinguished, then we can writez=uvwxy, such that:

1. vwx has at most n distinguished positions.

2. vx has at least one distinguished position.

3. For all i, uv^iwx^iy is in L.

Q: Use Odgen's lemma to show the following languages are notCFL's:

(a) { 0^i 1^j 0^k | j=max(i,k) }

(b) { a^n b^n c^i | i is not equal to n }

Answer rating: 100% (QA)

a Assume for the sake of contradiction that the language 0i 1j 0k jmaxik is a CFL Using Ogdens lemma ... View the full answer