En la informática teórica , en particular en la teoría del lenguaje formal , el teorema de Greibach establece que ciertas propiedades de las clases del 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 w1 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 a partir 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, utilizando 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 iniciales 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 manera finita mediante la siguiente gramática regular con el símbolo de inicio 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 idioma {ε, 1,3,4,6,9}, {} y {ε}, respectivamente.
El teorema de Greibach es independiente de un enfoque particular para describir un lenguaje formal. Solo 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 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.