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

1. x possui pelo menos uma posição marcada,
2. ou ambos u e v possuem posições marcadas, ou ambos y e z possuem posições marcadas,
3. vxy possui no máximo p posições marcadas, e
4. uvⁱxyⁱ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ⁱb^jc^kd^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.

Ver também

• Lema do bombeamento para linguagens livres de contexto
• Lema do bombeamento para linguagens regulares

Referências

• Ogden, W. (1968). «A helpful result for proving inherent ambiguity». Mathematical Systems Theory. 2 (3): 191–194. doi:10.1007/BF01694004 
• Hopcroft, Motwani and Ullman (1979). Automata Theory, Languages, and Computation. [S.l.]: Addison-Wesley. ISBN 8178083477