En la teoría del lenguaje formal, el lema de Ogden proporciona una extensión de la flexibilidad del lema de expansión para lenguajes libres de contexto .
El Lema de Ogden establece que si el lenguaje L es independiente del contexto, entonces existe un número p > 0 (donde p puede o no ser la longitud de la bomba) tal que para cualquier cadena w de longitud al menos p desde L y para cualquier "marcado" p o más posiciones en w , w puede representarse como
w = uvxyzdonde u , v , x , y y z son cadenas tales que
El Lema de Ogden se puede utilizar para demostrar que un idioma dado no está libre de contexto, en los casos en que el lema de crecimiento para idiomas libres de contexto no es suficiente. Un ejemplo sería el lenguaje { a i b j c k d l : i = 0 o j = k = l }. También es útil para probar la ambigüedad esencial de algunos idiomas.
Tenga en cuenta que si se marcan todas las posiciones, este lema es equivalente al lema de bombeo para lenguajes libres de contexto.
| Lenguajes formales y gramáticas formales | |
|---|---|
| Conceptos generales | |
| tipo 0 | |
| Tipo 1 |
|
| Tipo 2 | |
| tipo 3 |
|
| analizando | |