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.


Popular posts from this blog

Solved Exercises John C. Martin

Types of Turing Machines

Difference between DFA and NFA