Tuesday, June 26, 2012

Ogdens lemma

Ogden's lemma

Let L be a Context Free Language. Then there is a constant n such that if z is any word in L, and we mark any n or more positions of z  “distinguished” then we can write z = uvwxy such that:

(1) v and x together have atleast one distinguished position.

(2) vwx has at most n distinguished positions and

(3) for all i>=0  uviwxiy is in L.

No comments:

Post a Comment