Ogden's Lemma
Let L be a CFL. Then there is a constant p (same as the pumping lemma) such that if a word w is in L and we mark p or more positions of w as distinguished then we can write w = yxzuv such that:
1. yu together have at least 1 distinguished symbol.
2. yzu has at most p distinguished positions.
3. for all i >= 0, xy^izu^iv is in L. QED.
Note: Pomocí Pumping lemma nedokáži vyvrátit, že jazyk complement(L), kde L = {x^i y^j z^k | i = j or j = k }, není bezkontextový, ale pomocí tohoto lemmatu toho schopen jsem.
Zdroj: Professor Thomas A. Henzinger, předmět CS 172: Computability and Complexity, nápověda k problému 6.1(f), řešení problému (včetně i dalších důkazů pomocí pumping lemma pro bezkontextové jazyky.
Links to this Page