Lema de Ogden

En la teoría de los lenguajes formales , el lema de Ogden (llamado así por William F. Ogden) ^[1] es una generalización del lema de bombeo para lenguajes libres de contexto .

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 como "marcadas", existe un no terminal y una forma de dividir en 5 segmentos , como eso ${\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 en la mayoría de las posiciones marcadas. ${\displaystyle p}$

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

Usaremos subrayados para indicar posiciones "marcadas".

Casos especiales

El lema de Ogden a menudo se expresa de la siguiente forma, que puede obtenerse "olvidándose" de la gramática y concentrándose en el lenguaje mismo: si un lenguaje L está libre de contexto, entonces existe algún número (donde p puede o no ser 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 puede escribirse 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 el 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 están libres de contexto en los casos en que el lema de bombeo no es suficiente. Un ejemplo es el idioma . ${\displaystyle \{a^{i}b^{j}c^{k}d^{l}:i=0{\text{ or }}j=k=l\}}$

Aplicaciones de ejemplo

Sin contexto

El caso especial del lema de Ogden suele ser suficiente para demostrar que algunos lenguajes no están libres de contexto. Por ejemplo, es un ejemplo estándar de lenguaje no libre de contexto ( ^[2] , p. 128). ${\displaystyle \{a^{m}b^{n}c^{m}d^{n}|m,n\geq 1\}}$

Prueba

Supongamos que el lenguaje se genera mediante una gramática libre de contexto, luego sea la longitud requerida en el lema de Ogden y luego considere la palabra en el lenguaje. Entonces no pueden satisfacerse todas las tres condiciones implícitas en 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 está 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, que está implícita en el título del artículo de Ogden.

Ejemplo : Vamos . El lenguaje es inherentemente ambiguo. (Ejemplo de la página 3 del artículo 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 una verificació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}$

Por tanto, obtenemos una derivación de interpolando la derivación con copias de . Según esta derivación, una suboración completa desciende 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 completa que desciende 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 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, dejando que sea la constante del lema de Ogden, encontramos que tiene al menos diferentes análisis. Por 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, reduciéndolo al problema de la correspondencia postal . También puede mostrar que es indecidible decidir si un CFG tiene un grado ilimitado de ambigüedad inherente. (página 4 del artículo de Ogden)

Construcción

Dado cualquier problema de correspondencia postal sobre cadenas binarias, lo reducimos a un problema de decisión sobre un CFG.

Dadas dos listas cualesquiera de cadenas binarias y , reescriba el alfabeto binario en . ${\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 uno . Defina de manera similar . ${\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, según el mismo argumento anterior, el lenguaje es inherentemente ambiguo si el problema de la correspondencia del Post 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 la correspondencia del Post 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 ^[3] para permitir marcar algunas posiciones que no deben incluirse en vx . Posteriormente, Dömösi y Kudlek mejoraron su dependencia de los parámetros. ^[4] Si denotamos el número de dichas 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 una constante que depende sólo del idioma. La afirmación es que cada s se puede escribir 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, cada uno de u,v,w tiene una posición marcada, o cada uno 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. Hopcroft, John E. (1979). Introducción a la teoría de los autómatas, los lenguajes y la computación. Jeffrey D. Ullman. Lectura, Massachusetts: Addison-Wesley. ISBN 0-201-02988-X. OCLC  4549363.
3. Bader, Cristóbal; 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.
4. Dömösi, Pál; Kudlek, Manfred (1999), "Lemas de iteración fuertes para lenguajes indexados regulares, lineales, libres de contexto y lineales", Fundamentos de la teoría de la computación , Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 226–233, doi :10.1007/3 -540-48321-7_18, ISBN 978-3-540-66412-3, recuperado el 26 de febrero de 2023