En informática teórica , en particular en teoría del lenguaje formal , el teorema de Greibach establece que ciertas propiedades de las clases de lenguaje formal son indecidibles . Lleva el nombre de la científica informática Sheila Greibach , quien lo demostró por primera vez en 1963. [1] [2]
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 cuerda 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 del lenguaje formal para denotar un lenguaje formal mediante una descripción finita, como una gramática formal o una máquina de estados finitos .
Por ejemplo, usando un alfabeto Σ = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, el conjunto Σ * consta de todos (representaciones decimales de) números naturales, con ceros a la izquierda permitidos, y la cadena vacía, denotada como ε. El conjunto L div3 de todos los naturales divisibles por 3 es un lenguaje formal infinito sobre Σ; se puede describir de forma finita 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.
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
Sea P cualquier subconjunto no trivial de C que contenga todos los conjuntos regulares sobre Σ∪{#} y esté cerrado bajo el cociente por cada símbolo en Σ∪{#}. [nota 2] Entonces la cuestión de si L ∈ P para una descripción dada de un lenguaje L ∈ C es indecidible.
Sea M ⊆ Σ * , tal que M ∈ C , pero M ∉ P . [nota 3] Para cualquier L ∈ C con L ⊆ Σ * , defina φ( L ) = ( M #Σ * ) ∪ (Σ * # L ). A partir de una descripción de L , se puede calcular efectivamente una descripción de φ( L ).
Entonces L = Σ * si y sólo si φ( L ) ∈ P :
Por lo tanto, si la pertenencia a P sería 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 que contradice la definición de C. [3]
Utilizando el teorema de Greibach, se puede demostrar que los siguientes problemas son indecidibles:
Véase también Gramática libre de contexto#Estar en un nivel inferior o superior de la jerarquía de Chomsky .