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. 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

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