En la teoría de lenguajes formales , el lema de Ogden (llamado así en honor a William F. Ogden) [1] es una generalización del lema de bombeo para lenguajes libres de contexto .
A pesar de que el lema de Ogden es un fortalecimiento del lema de bombeo, es insuficiente para caracterizar completamente la clase de lenguajes libres de contexto. [2] Esto contrasta con el teorema de Myhill-Nerode , que a diferencia del lema de bombeo para los lenguajes regulares es una condición necesaria y suficiente para la regularidad.
Lema de Ogden : Si un lenguaje se genera mediante una gramática libre de contexto , entonces existe algo tal que con longitud , y cualquier forma de marcar posiciones de como "marcadas", existe un no terminal y una forma de dividir en 5 segmentos , tal que
contiene al menos una posición marcada.
contiene como máximo las posiciones marcadas.
ambos contienen posiciones marcadas, o ambos contienen posiciones marcadas.
Utilizaremos subrayados para indicar posiciones "marcadas".
El lema de Ogden se enuncia a menudo en la siguiente forma, que se puede obtener "olvidándose" de la gramática y concentrándose en el lenguaje en sí: Si un lenguaje L es libre de contexto, entonces existe algún número (donde p puede ser o no una longitud de bombeo) tal que para cualquier cadena s de longitud al menos p en L y cada forma de "marcar" p o más de las posiciones en s , s se puede escribir como
con cadenas u, v, w, x e y , tales que
En el caso especial en que cada posición está marcada, el lema de Ogden es equivalente al lema de bombeo para lenguajes libres de contexto. El lema de Ogden se puede utilizar para mostrar que ciertos lenguajes no son libres de contexto en casos en que el lema de bombeo no es suficiente. Un ejemplo es el lenguaje .
El caso especial del lema de Ogden suele ser suficiente para demostrar que algunos lenguajes no son independientes del contexto. Por ejemplo, es un ejemplo estándar de lenguaje no independiente del contexto, [3]
Supongamos que el lenguaje se genera mediante una gramática independiente del contexto, entonces sea la longitud requerida en el lema de Ogden, y luego consideremos la palabra en el lenguaje. Entonces, no se pueden satisfacer todas las tres condiciones implicadas por el lema de Ogden.
De manera similar, se puede demostrar que el lenguaje "copiar dos veces" no es libre de contexto, utilizando el lema de Ogden en .
Y el ejemplo dado en la última sección no está libre de contexto al utilizar el lema de Ogden en .
El lema de Ogden se puede utilizar para demostrar la ambigüedad inherente de algunos lenguajes, lo cual está implícito en el título del artículo de Ogden.
Ejemplo : Sea . El lenguaje es inherentemente ambiguo. (Ejemplo de la página 3 del trabajo de Ogden).
Sea la longitud de bombeo necesaria para el lema de Ogden y aplíquela a la oración .
Mediante la comprobación rutinaria de las condiciones del lema de Ogden, encontramos que la derivación es
donde , satisfactorio y y .
De esta manera, obtenemos una derivación de interpolando la derivación con copias de . De acuerdo con esta derivación, una suboración completa es descendiente de un nodo en el árbol de derivación.
Simétricamente, podemos obtener otra derivación de , según la cual hay una suboración entera que es descendiente de un nodo en el árbol de derivación.
Dado que las dos suboraciones tienen una intersección no vacía, y dado que ninguna contiene a la otra, los dos árboles de derivación son diferentes.
De manera similar, es inherentemente ambiguo y, para cualquier CFG del lenguaje, siendo que sea la constante del lema de Ogden, encontramos que tiene al menos diferentes análisis. Por lo tanto, tiene un grado ilimitado de ambigüedad inherente.
La prueba puede ampliarse para mostrar que decidir si un CFG es inherentemente ambiguo es indecidible, por reducción al problema de correspondencia de Post . También puede mostrar que decidir si un CFG tiene un grado ilimitado de ambigüedad inherente es indecidible. (página 4 del artículo de Ogden)
Dado cualquier problema de correspondencia posterior sobre cadenas binarias, lo reducimos a un problema de decisión sobre un CFG.
Dadas dos listas de cadenas binarias y , reescribe el alfabeto binario como .
Sea el lenguaje sobre alfabeto , generado por el CFG con reglas para cada . De manera similar, defina .
Ahora bien, por el mismo argumento expuesto anteriormente, el lenguaje es inherentemente ambiguo si y solo si el problema de correspondencia postal tiene una solución.
Y el lenguaje tiene un grado ilimitado de ambigüedad inherente si el problema de correspondencia postal tiene solución.
Bader y Moura han generalizado el lema [4] para permitir marcar algunas posiciones que no deben incluirse en vx . Su dependencia de los parámetros fue mejorada posteriormente por Dömösi y Kudlek. [5] Si denotamos el número de tales posiciones excluidas por e , entonces el número d de posiciones marcadas de las cuales queremos incluir algunas en vx debe satisfacer , donde p es alguna constante que depende solo del lenguaje. La afirmación se convierte en que cada s puede escribirse como
con cadenas u, v, w, x e y , tales que
Además, o bien cada uno de u,v,w tiene una posición marcada, o bien cada uno de tiene una posición marcada.