Estoy buscando idiomas que "probablemente no estén libres de contexto" pero no podemos (des) probarlo usando técnicas estándar conocidas.
¿Hay una encuesta reciente sobre el tema o una sección de problemas abierta de una conferencia reciente?
Probablemente no haya muchos idiomas que no se sepa que son CF, por lo que si conoce uno también puede publicarlo como respuesta.
Los ejemplos que encontré son:
- el lenguaje bien conocido de las palabras primitivas (hay un libro reciente bastante bueno sobre él: Lenguajes libres de contexto y palabras primitivas )
- las representaciones de Base-k del codominio de un polinomio (vea la pregunta " Representaciones de Base-k del co-dominio de un polinomio - ¿está libre de contexto? " en teoría, que tal vez haya sido resuelta por domotorp, vea su preimpresión )
Nota : como lo muestra Aryeh en su respuesta, puede construir una clase completa de dichos lenguajes si "vincula" un lenguaje a una conjetura desconocida sobre la (no) finitud o (no) vacío de algunos conjuntos (por ejemplo, no puede expresarse como una suma de dos primos ). No estoy muy interesado en tales ejemplos.
reference-request
big-list
context-free
Marzio De Biasi
fuente
fuente
Respuestas:
Otra buena es el complemento del conjuntoS de subpalabras contiguas (también conocidos como "factores") de la secuencia Thue-Morse t =0110100110010110⋯ . Para dar un poco de contexto, Jean Berstel demostró que el complemento del conjunto T de prefijos de la palabra Thue-Morse no tiene contexto (y en realidad es algo más general que eso). Pero el resultado correspondiente para las subpalabras todavía está abierto.
fuente
¿Qué tal el lenguajeLTPAGS de primos gemelos? Es decir, todos los pares de números naturales ( p , p′) (representados, digamos, en unario), de modo que p , p′ son primos y pags′= p + 2 ? Si la conjetura de primos gemelos es verdadera, entonces LTPAGS no está libre de contexto; de lo contrario, es finito.
Editar: Permítanme dar un bosquejo de prueba rápida de que la conjetura de los primos gemelos implica queLTPAGS no está libre de contexto. Asociado a cualquier idioma L su secuencia de longitud 0 ≤ a1≤ a2≤ ... , donde el entero ℓ aparece en la secuencia si y sólo si hay una palabra de longitud ℓ en L . Es una consecuencia de los lemas de bombeo que para L que son regulares o CFL, la secuencia de longitud satisface la propiedad de diferencias limitadas: hay un R > 0 tal que an+1−an≤R para todon . Es un hecho fácil y bien conocido en la teoría de números que los números primos no tienen diferencias acotadas. Finalmente, cualquier subsecuencia infinita de una secuencia que viole la propiedad de diferencias limitadas en sí misma debe violarla.
fuente