Lema de Ogden

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.

Declaración

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 ${\displaystyle L}$ ${\displaystyle p\geq 1}$ ${\displaystyle \forall w\in L}$ ${\displaystyle \geq p}$ ${\displaystyle \geq p}$ ${\displaystyle w}$ ${\displaystyle A}$ ${\displaystyle w}$ ${\displaystyle uxzyv}$

$${\displaystyle S\Rightarrow ^{*}uAv\Rightarrow ^{*}uxAyv\Rightarrow ^{*}uxzyv}$$

${\displaystyle z}$contiene al menos una posición marcada.

${\displaystyle xzy}$contiene como máximo las posiciones marcadas. ${\displaystyle p}$

${\displaystyle u,x}$ambos contienen posiciones marcadas, o ambos contienen posiciones marcadas. ${\displaystyle y,v}$

Utilizaremos subrayados para indicar posiciones "marcadas".

Casos especiales

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 ${\displaystyle p\geq 1}$

${\displaystyle s=uvwxy}$

con cadenas u, v, w, x e y , tales que

1. vx tiene al menos una posición marcada,
2. vwx tiene como máximo p posiciones marcadas, y
3. ${\displaystyle uv^{n}wx^{n}y\in L}$Para todos . ${\displaystyle n\geq 0}$

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 . ${\displaystyle \{a^{i}b^{j}c^{k}d^{l}:i=0{\text{ or }}j=k=l\}}$

Ejemplos de aplicaciones

No libre de contexto

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] ${\displaystyle \{a^{m}b^{n}c^{m}d^{n}|m,n\geq 1\}}$

Prueba

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. ${\displaystyle p}$ ${\displaystyle a^{p}{\underline {b^{p}c^{p}}}d^{p}}$

De manera similar, se puede demostrar que el lenguaje "copiar dos veces" no es libre de contexto, utilizando el lema de Ogden en . ${\displaystyle L=\{w^{2}|w\in \{a,b\}^{*}\}}$ ${\displaystyle a^{2p}{\underline {b^{2p}}}a^{2p}b^{2p}}$

Y el ejemplo dado en la última sección no está libre de contexto al utilizar el lema de Ogden en . ${\displaystyle \{a^{i}b^{j}c^{k}d^{l}:i=0{\text{ or }}j=k=l\}}$ ${\displaystyle ab^{2p}{\underline {c^{2p}}}d^{2p}}$

Ambigüedad inherente

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). ${\displaystyle L_{0}=\{a^{n}b^{m}c^{m}|m,n\geq 1\},L_{1}=\{a^{m}b^{m}c^{n}|m,n\geq 1\}}$ ${\displaystyle L=L_{0}\cup L_{1}}$

Prueba

Sea la longitud de bombeo necesaria para el lema de Ogden y aplíquela a la oración . ${\displaystyle p}$ ${\displaystyle a^{p!+p}{\underline {b^{p}c^{p}}}}$

Mediante la comprobación rutinaria de las condiciones del lema de Ogden, encontramos que la derivación es

$${\displaystyle S\Rightarrow ^{*}uAv\Rightarrow ^{*}uxAyv\Rightarrow ^{*}uxzyv}$$donde , satisfactorio y y . ${\displaystyle u=a^{p!+p}b^{p-s-k},x=b^{k},z=b^{s}c^{s'},y=c^{k},v=c^{p-s'-k}}$ ${\displaystyle s+s'\geq 1}$ ${\displaystyle k\geq 1}$ ${\displaystyle p\geq s+s'+2k}$

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. ${\displaystyle a^{p!+p}b^{p!+p}c^{p!+p}}$ ${\displaystyle p!/k}$ ${\displaystyle A\Rightarrow ^{*}xAy}$ ${\displaystyle x^{p!/k+1}zy^{p!/k+1}=b^{p!+k+s}c^{p!+k+s'}}$ ${\displaystyle A}$

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. ${\displaystyle a^{p!+p}b^{p!+p}c^{p!+p}}$ ${\displaystyle a^{p!+k''+s''}b^{p!+k''+s'''}}$

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. ${\displaystyle (p!+k+s)+(p!+k''+s''')>2p!+1>p!+p}$

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. ${\displaystyle L^{*}}$ ${\displaystyle p}$ ${\displaystyle (a^{p!+p}b^{p!+p}c^{p!+p})^{n}}$ ${\displaystyle 2^{n}}$ ${\displaystyle L^{*}}$

Indecidibilidad

La prueba puede ampliarse para mostrar que decidir si un CFG es inherentemente ambiguo es indecidible, mediante 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)

Construcción

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 . ${\displaystyle \xi _{1},...,\xi _{n}}$ ${\displaystyle \eta _{1},...,\eta _{n}}$ ${\displaystyle \{d,e\}}$

Sea el lenguaje sobre alfabeto , generado por el CFG con reglas para cada . De manera similar, defina . ${\displaystyle L\left(\xi _{1},\cdots ,\xi _{n}\right)}$ ${\displaystyle \{d,e,f\}}$ ${\displaystyle S\to \xi _{i}Sd^{i}e|f}$ ${\displaystyle i=1,...,n}$ ${\displaystyle L\left(\eta _{1},\cdots ,\eta _{n}\right)}$

Ahora bien, por el mismo argumento expuesto anteriormente, el lenguaje es inherentemente ambiguo si el problema de correspondencia postal tiene una solución. ${\displaystyle (L_{0}\cdot L\left(\xi _{1},\cdots ,\xi _{n}\right))\cup (L_{1}\cdot L\left(\eta _{1},\cdots ,\eta _{n}\right))}$

Y el lenguaje tiene un grado ilimitado de ambigüedad inherente si el problema de correspondencia posterior tiene una solución. ${\displaystyle ((L_{0}\cdot L\left(\xi _{1},\cdots ,\xi _{n}\right))\cup (L_{1}\cdot L\left(\eta _{1},\cdots ,\eta _{n}\right)))^{*}}$

Condición generalizada

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 ${\displaystyle d\geq p(e+1)}$

${\displaystyle s=uvwxy}$

con cadenas u, v, w, x e y , tales que

1. vx tiene al menos una posición marcada y ninguna posición excluida,
2. vwx tiene como máximo posiciones marcadas, y ${\displaystyle p^{(e+1)}}$
3. ${\displaystyle uv^{n}wx^{n}y\in L}$Para todos . ${\displaystyle n\geq 0}$

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. ${\displaystyle w,x,y}$

Referencias

1. Ogden, William (septiembre de 1968). "Un resultado útil para demostrar la ambigüedad inherente". Teoría de sistemas matemáticos . 2 (3): 191–194. doi :10.1007/bf01694004. ISSN  0025-5661. S2CID  13197551.
2. Kracht, Marcus (2004). Too Many Languages ​​Satisfy Ogden's Lemma (PDF) . Actas del 27.º Coloquio de Lingüística de Pensilvania. Filadelfia. págs. 115–121 . Consultado el 16 de mayo de 2024 .
3. Hopcroft, John E. (1979). Introducción a la teoría de autómatas, lenguajes y computación. Jeffrey D. Ullman. Reading, Mass.: Addison-Wesley. pág. 128. ISBN 0-201-02988-X.OCLC 4549363  .
4. Bader, Christopher; Moura, Arnaldo (abril de 1982). "Una generalización del lema de Ogden". Matemáticas Aplicadas y Computación . 29 (2): 404–407. doi : 10.1145/322307.322315 . S2CID  33988796.
5. Dömösi, Pál; Kudlek, Manfred (1999), "Lemas de iteración fuertes para lenguajes regulares, lineales, libres de contexto y lineales indexados", Fundamentals of Computation Theory , Berlín, Heidelberg: Springer Berlin Heidelberg, pp. 226–233, doi :10.1007/3-540-48321-7_18, ISBN 978-3-540-66412-3, consultado el 26 de febrero de 2023