write summary on Ogden’s Lemma
Answers
Ogden's lemma states that if a language L is context-free, then there exists some number {\displaystyle p\geq 1}{\displaystyle p\geq 1} (where p may or may not be a pumping length) such that for any string s of length at least p in L and every way of "marking" p or more of the positions in s, s can be written as
{\displaystyle s=uvwxy}{\displaystyle s=uvwxy}
with strings u, v, w, x, and y, such that
vx has at least one marked position,
vwx has at most p marked positions, and
{\displaystyle uv^{n}wx^{n}y\in L}{\displaystyle uv^{n}wx^{n}y\in L} for all {\displaystyle n\geq 0}n\geq 0.
In the special case where every position is marked, Ogden's lemma is equivalent to the pumping lemma for context-free languages. Ogden's lemma can be used to show that certain languages are not context-free in cases where the pumping lemma is not sufficient. An example is the language {\displaystyle \{a^{i}b^{j}c^{k}d^{l}:i=0{\text{ or }}j=k=l\}}{\displaystyle \{a^{i}b^{j}c^{k}d^{l}:i=0{\text{ or }}j=k=l\}}. Ogden's lemma can also be used to prove the inherent ambiguity of some languages.[citation needed