Ogden's lemma : If L is a CFL, then there is a constant n, suchthat if z
Fantastic news! We've Found the answer you've been seeking!
Question:
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 }
Related Book For
Posted Date: