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 uvixyiz 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 {aibjckdl : 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.
Ver também Lema do bombeamento para linguagens livres de contexto Lema do bombeamento para linguagens regulares
Referências
Categoria:Linguagens formais