Hispanopedia Wiki
Articulo de referencia

Teorema de Greibach

En informática teórica , en particular en la teoría de lenguajes formales , el teorema de Greibach establece que ciertas propiedades de las clases de lenguajes formales son inde...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática teórica , en particular en la teoría de lenguajes formales , el teorema de Greibach establece que ciertas propiedades de las clases de lenguajes formales son indecidibles . Recibe su nombre de la científica informática Sheila Greibach , quien lo demostró por primera vez en 1963. [ 1 ] [ 2 ]

Definiciones

Dado un conjunto Σ, a menudo llamado "alfabeto", el conjunto (infinito) de todas las cadenas construidas a partir de miembros de Σ se denota por Σ * . Un lenguaje formal es un subconjunto de Σ * . Si L 1 y L 2 son lenguajes formales, su producto L 1 L 2 se define como el conjunto { w 1 w 2  : w 1 ∈ L 1 , w 2 ∈ L 2 } de todas las concatenaciones de una cadena w 1 de L 1 con una cadena w 2 de L 2 . Si L es un lenguaje formal y a es un símbolo de Σ, su cociente L / a se define como el conjunto { w  : wa ∈ L } de todas las cadenas que pueden convertirse en miembros de L añadiendo una a . Se conocen varios enfoques de la teoría de lenguajes formales para denotar un lenguaje formal mediante una descripción finita, como una gramática formal o una máquina de estados finitos .

Por ejemplo, utilizando un alfabeto Σ = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, el conjunto Σ * consta de todos los números naturales (o sus representaciones decimales), permitiendo ceros iniciales, y la cadena vacía, denotada como ε. El conjunto L div3 de todos los números naturales divisibles por 3 es un lenguaje formal infinito sobre Σ; puede describirse finitamente mediante la siguiente gramática regular con símbolo inicial S 0 :

Ejemplos de lenguajes finitos son {ε,1,2} y {0,2,4,6,8}; su producto {ε,1,2}{0,2,4,6,8} produce los números pares hasta 28. El cociente del conjunto de números primos hasta 100 por el símbolo 7, 4 y 2 produce el lenguaje {ε,1,3,4,6,9}, {} y {ε}, respectivamente.

Enunciado formal del teorema

El teorema de Greibach es independiente de un enfoque particular para describir un lenguaje formal. Simplemente considera un conjunto C de lenguajes formales sobre un alfabeto Σ∪{#} tal que

  • Cada lenguaje en C tiene una descripción finita,
  • cada lenguaje regular sobre Σ∪{#} está en C , [ nota 1 ]
  • Dadas las descripciones de los lenguajes L 1 , L 2 ∈ C y de un lenguaje regular R ∈ C , se puede calcular eficazmente una descripción de los productos L 1 R y RL 1 , y de la unión L 1 ∪ L 2 , y
  • Es indecidible para cualquier lenguaje miembro L ∈ C con L ⊆ Σ * si L = Σ * .

Sea P cualquier subconjunto no trivial de C que contiene todos los conjuntos regulares sobre Σ∪{#} y es cerrado bajo el cociente por cada símbolo individual en Σ∪{#}. [ nota 2 ] Entonces, la pregunta de si L ∈ P para una descripción dada de un lenguaje L ∈ C es indecidible.

Prueba

Sea M ⊆ Σ * , tal que M ∈ C , pero M ∉ P . [ nota 3 ] Para cualquier L ∈ C con L ⊆ Σ * , definimos φ( L ) = ( M #Σ * ) ∪ (Σ * # L ). A partir de una descripción de L , se puede calcular eficazmente una descripción de φ( L ).

Entonces L = Σ * si y solo si φ( L ) ∈ P :

  • Si L = Σ * , entonces φ( L ) = Σ * #Σ * es un lenguaje regular y, por tanto, en P .
  • De lo contrario, existe algún w ∈ Σ * \ L , y el cociente φ( L )/(# w ) es igual a M . Por lo tanto, mediante la aplicación repetida de la propiedad de cierre del cociente, φ( L ) ∈ P implicaría M = φ( L )/(# w ) ∈ P , lo que contradice la definición de M .

Por lo tanto, si la pertenencia a P fuera decidible para φ( L ) a partir de su descripción, también lo sería la igualdad de L con Σ * a partir de su descripción, lo cual contradice la definición de C . [ 3 ]

Aplicaciones

Utilizando el teorema de Greibach, se puede demostrar que los siguientes problemas son indecidibles:

Demostración: La clase de lenguajes libres de contexto y el conjunto de lenguajes regulares satisfacen las propiedades anteriores de C y P , respectivamente. [ nota 4 ] [ 4 ]
Prueba: La clase de lenguajes libres de contexto, y el conjunto de lenguajes libres de contexto que no son inherentemente ambiguos, satisfacen las propiedades anteriores de C y P , respectivamente. [ 5 ]

Véase también Gramática libre de contexto#Estar en un nivel inferior o superior de la jerarquía de Chomsky .

Notas

  1. ↑ Esto se deja implícito en Hopcroft, Ullman, 1979: P ⊆ C necesita contener todos estos lenguajes regulares.
  2. ↑ Es decir, si L ∈ P , entonces L / a ∈ P para cada a ∈ Σ∪{#}.
  3. ↑ La existencia de tal M es requerida por el requisito anterior, algo vago, de que P sea "no trivial".
  4. ↑ Los lenguajes regulares son libres de contexto: Gramática libre de contexto#Subclases ; los lenguajes libres de contexto son cerrados con respecto a la unión y la concatenación (incluso general): Gramática libre de contexto#Propiedades de cierre ; la igualdad con Σ * es indecidible para lenguajes libres de contexto: Gramática libre de contexto#Universalidad ; los lenguajes regulares son cerrados bajo cocientes (incluso generales): Lenguaje regular#Propiedades de cierre .

Referencias

  1. ↑ Sheila Greibach (1963). "La indecidibilidad del problema de la ambigüedad para gramáticas lineales mínimas". Information and Control . 6 (2): 117– 125. doi : 10.1016/s0019-9958(63)90149-9 .
  2. ↑ Sheila Greibach (1968). "Una nota sobre las propiedades indecidibles de los lenguajes formales". Math Systems Theory . 2 (1): 1– 6. doi : 10.1007/bf01691341 . S2CID 19948229 . 
  3. ↑ John E. Hopcroft ; Jeffrey D. Ullman (1979). Introducción a la teoría de autómatas, lenguajes y computación . Addison-Wesley. ISBN 0-201-02988-X.págs. 205-206
  4. ↑ Hopcroft, Ullman, 1979, pág. 205, Teorema 8.15
  5. ↑ Hopcroft, Ullman, 1979, pág. 206, Teorema 8.16