Lema de Ogden

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  • 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. Automata Theory, Languages, and Computation. [S.l.]: Addison-Wesley, 1979. ISBN 8178083477