Hispanopedia Wiki
Articulo de referencia

El lema de Ogden

En la teoría de los 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 conte...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría de los 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 lenguajes regulares, es una condición necesaria y suficiente para la regularidad.

Declaración

Lema de Ogden : si un idiomaL{\displaystyle L}es generado por una gramática libre de contexto , entonces existe algúnpag≥1{\displaystyle p\geq 1}de tal manera que para cadaw∈L{\displaystyle w\in L}con|w|≥pag{\displaystyle |w|\geq p}y para cualquier marcaje depag{\displaystyle p}o más puestos enw{\displaystyle w}, existe un no terminalA{\displaystyle A}de la gramática y una forma de dividirw{\displaystyle w}en 5 segmentostúincógnitazyv{\displaystyle uxzyv}, de tal manera que

S⇒∗túAv⇒∗túincógnitaAyv⇒∗túincógnitazyv{\displaystyle S\Rightarrow ^{*}uAv\Rightarrow ^{*}uxAyv\Rightarrow ^{*}uxzyv}

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

incógnitazy{\displaystyle xzy}contiene como máximopag{\displaystyle p}posiciones marcadas.

tú,incógnita{\displaystyle u,x}ambos contienen posiciones marcadas, oy,v{\displaystyle y,v}Ambos contienen posiciones marcadas.

Utilizaremos subrayados para indicar las posiciones "marcadas".

Casos especiales

El lema de Ogden se suele enunciar de la siguiente forma, que se puede obtener "olvidándose" de la gramática y concentrándose en el lenguaje mismo: Si un lenguaje L es libre de contexto, entonces existe algún númeropag≥1{\displaystyle p\geq 1}(donde p puede o no ser una longitud de bombeo) de tal manera que para cualquier cadena s de longitud al menos p en L y cualquier forma de "marcar" p o más de las posiciones en s , s se puede escribir como

s=túvwincógnitay{\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. túvnortewincógnitanortey∈L{\displaystyle uv^{n}wx^{n}y\in L}a pesar denorte≥0{\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 usar para demostrar que ciertos lenguajes no son libres de contexto en casos donde el lema de bombeo no es suficiente. Un ejemplo es el lenguaje{aibjdokdl:i=0 o j=k=l}{\displaystyle \{a^{i}b^{j}c^{k}d^{l}:i=0{\text{ o }}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 libres de contexto. Por ejemplo,{ametrobnortedometrodnorte|metro,norte≥1}{\displaystyle \{a^{m}b^{n}c^{m}d^{n}|m,n\geq 1\}}es un ejemplo estándar de lenguaje no libre de contexto, [ 3 ]

Prueba

Supongamos que el lenguaje es generado por una gramática libre de contexto, entonces sea:pag{\displaystyle p}Sea la longitud requerida en el lema de Ogden, entonces considere la palabraapagbpagdopag_dpag{\displaystyle a^{p}{\underline {b^{p}c^{p}}}d^{p}}en el idioma. Entonces, las tres condiciones implícitas en el lema de Ogden no pueden cumplirse todas.

De manera similar, se puede demostrar el lenguaje "copiar dos veces".L={w2|w∈{a,b}∗}{\displaystyle L=\{w^{2}|w\in \{a,b\}^{*}\}}no es libre de contexto, al usar el lema de Ogden ena2pagb2pag_a2pagb2pag{\displaystyle a^{2p}{\underline {b^{2p}}}a^{2p}b^{2p}}.

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

Ambigüedad inherente

El lema de Ogden puede utilizarse para demostrar la ambigüedad inherente de algunos lenguajes, tal como lo sugiere el título del artículo de Ogden.

Ejemplo : DejemosL0={anortebmetrodometro|metro,norte≥1},L1={ametrobmetrodonorte|metro,norte≥1}{\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\}}El idiomaL=L0∪L1{\displaystyle L=L_{0}\cup L_{1}}es inherentemente ambiguo. (Ejemplo de la página 3 del artículo de Ogden).

Prueba

Dejarpag{\displaystyle p}sea ​​la longitud de bombeo necesaria para el lema de Ogden, y aplíquela a la oración.apag¡+pagbpagdopag_{\displaystyle a^{p!+p}{\underline {b^{p}c^{p}}}}.

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

S⇒∗túAv⇒∗túincógnitaAyv⇒∗túincógnitazyv{\displaystyle S\Rightarrow ^{*}uAv\Rightarrow ^{*}uxAyv\Rightarrow ^{*}uxzyv} dóndetú=apag¡+pagbpag−s−k,incógnita=bk,z=bsdos′,y=dok,v=dopag−s′−k{\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}}, satisfactorios+s′≥1{\displaystyle s+s'\geq 1}yk≥1{\displaystyle k\geq 1}ypag≥s+s′+2k{\displaystyle p\geq s+s'+2k}.

Así, obtenemos una derivación deapag¡+pagbpag¡+pagdopag¡+pag{\displaystyle a^{p!+p}b^{p!+p}c^{p!+p}}interpolando la derivación conpag¡/k{\displaystyle p!/k}copias deA⇒∗incógnitaAy{\displaystyle A\Rightarrow ^{*}xAy}. Según esta derivación, una suboración completaincógnitapag¡/k+1zypag¡/k+1=bpag¡+k+sdopag¡+k+s′{\displaystyle x^{p!/k+1}zy^{p!/k+1}=b^{p!+k+s}c^{p!+k+s'}}es descendiente de un nodoA{\displaystyle A}en el árbol de derivación.

De forma simétrica, podemos obtener otra derivación de apag¡+pagbpag¡+pagdopag¡+pag{\displaystyle a^{p!+p}b^{p!+p}c^{p!+p}}, según la cual hay una suboración completaapag¡+k″+s″bpag¡+k″+s‴{\displaystyle a^{p!+k''+s''}b^{p!+k''+s'''}}ser descendiente de un nodo en el árbol de derivación.

Desde(pag¡+k+s)+(pag¡+k″+s‴)>2pag¡+1>pag¡+pag{\displaystyle (p!+k+s)+(p!+k''+s''')>2p!+1>p!+p}Las dos suboraciones tienen una intersección no vacía, y como ninguna contiene a la otra, los dos árboles de derivación son diferentes.

Similarmente,L∗{\displaystyle L^{*}}es inherentemente ambiguo, y para cualquier gramática libre de contexto del lenguaje, dejarpag{\displaystyle p}Sea la constante del lema de Ogden, encontramos que(apag¡+pagbpag¡+pagdopag¡+pag)norte{\displaystyle (a^{p!+p}b^{p!+p}c^{p!+p})^{n}}tiene al menos2norte{\displaystyle 2^{n}}diferentes análisis. Por lo tantoL∗{\displaystyle L^{*}}posee un grado ilimitado de ambigüedad inherente.

Indecidibilidad

La demostración puede extenderse para mostrar que decidir si una gramática libre de contexto (GLC) es inherentemente ambigua es indecidible, mediante reducción al problema de correspondencia de Post . También puede mostrar que decidir si una GLC 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 de Post sobre cadenas binarias, lo reducimos a un problema de decisión sobre una gramática libre de contexto (GLC).

Dadas dos listas cualesquiera de cadenas binariasξ1,...,ξnorte{\displaystyle \xi _{1},...,\xi _{n}}yη1,...,ηnorte{\displaystyle \eta _{1},...,\eta _{n}}, reescribe el alfabeto binario a{d,mi}{\displaystyle \{d,e\}}.

DejarL(ξ1,⋯,ξnorte){\displaystyle L\left(\xi _{1},\cdots ,\xi _{n}\right)}ser el lenguaje sobre el alfabeto{d,mi,F}{\displaystyle \{d,e,f\}}, generado por el CFG con reglasS→ξiSdimi|F{\displaystyle S\to \xi _{i}Sd^{i}e|f}por cadai=1,...,norte{\displaystyle i=1,...,n}. De manera similar definaL(η1,⋯,ηnorte){\displaystyle L\left(\eta _{1},\cdots ,\eta _{n}\right)}.

Ahora, siguiendo el mismo argumento anterior, el lenguaje(L0⋅L(ξ1,⋯,ξnorte))∪(L1⋅L(η1,⋯,ηnorte)){\displaystyle (L_{0}\cdot L\left(\xi _{1},\cdots ,\xi _{n}\right))\cup (L_{1}\cdot L\left(\eta _{1},\cdots ,\eta _{n}\right))}es inherentemente ambiguo si y solo si el problema de correspondencia postal tiene una solución.

Y el idioma((L0⋅L(ξ1,⋯,ξnorte))∪(L1⋅L(η1,⋯,ηnorte)))∗{\displaystyle ((L_{0}\cdot L\left(\xi _{1},\cdots ,\xi _{n}\right))\cup (L_{1}\cdot L\left(\eta _{1},\cdots ,\eta _{n}\right)))^{*}}tiene un grado ilimitado de ambigüedad inherente si y solo si el problema de correspondencia de Post tiene una solución.

Afecció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 dichas posiciones excluidas por e , entonces el número d de posiciones marcadas debe satisfacerd≥pag(mi+1){\displaystyle d\geq p^{(e+1)}}, donde p es una constante que depende únicamente del lenguaje. La afirmación se convierte en que cada s puede escribirse como

s=túvwincógnitay{\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. Dejarr{\displaystyle r}sea ​​el número de posiciones marcadas ys{\displaystyle s}el número de posiciones excluidas en vwx ; entoncesr≤pags+1{\displaystyle r\leq p^{s+1}}.
  3. túvnortewincógnitanortey∈L{\displaystyle uv^{n}wx^{n}y\in L}a pesar denorte≥0{\displaystyle n\geq 0}.

Referencias

  1. ↑ Ogden, William (septiembre de 1968). "Un resultado útil para probar la ambigüedad inherente" . Mathematical Systems Theory . 2 (3): 191– 194. doi : 10.1007/bf01694004 . ISSN 0025-5661 . S2CID 13197551 .  
  2. ↑ Kracht, Marcus (2004). Demasiados idiomas satisfacen el lema de Ogden ( 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. 128. ISBN  0-201-02988-XOCLC 4549363​​ 
  4. ↑ Bader, Christopher; Moura, Arnaldo (abril de 1982). "Una generalización del lema de Ogden" . Journal of the ACM . 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 indexados regulares, lineales, libres de contexto y lineales" , Fundamentos de la teoría de la computación , 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