Lema de Ogden
# Lema de Ogden

Acerca da teoria de Linguagens Formais, o Lema de Ogden provê uma aumento de flexibilidade sobre o lema do bombeamento para linguagens livres de contexto.
O Lema de Ogden descreve que se uma linguagem L é livre de contexto, então existe algum número p > 0 (onde p pode ou não ser um comprimento de bombeamento) tal que para qualquer cadeia w de comprimento pelo menos p e contida em L, e para qualquer maneira de "marcar" p ou mais entre as posições em w, w pode ser escrito como
    w = uvxyz
com cadeias u, v, x, y e z, tais que
* x possui pelo menos uma posição marcada,
* ou ambos u e v possuem posições marcadas, ou ambos y e z possuem posições marcadas,
* vxy possui no máximo p posições marcadas, e
* uv$^i$xy$^i$z está contida em L, para todo i ≥ 0.
O Lema de Ogden pode ser usado para demonstrar que certas linguagens não são livres de contexto, em casos onde o lema do bombeamento para linguagens livres de contexto não é suficiente. Um exemplo é a linguagem {a$^i$b$^j$c$^k$d$^l$ : i = 0 ou j = k = l}. Também é útil para provar a ambiguidade inerente de algumas linguagens.
Observe que, quando todas as posições estão marcadas, o Lema de Ogden é equivalente ao lema do bombeamento para linguagens livres de contexto.