El lenguaje de los prefijos del lenguaje sensible al contexto es sensible al contexto

Question

Given es un lenguaje sensible al contexto $L$ . ¿Es la lengua ${\sf pref}(L)$ que contiene todos los prefijos de $L$ palabras, también sensibles al contexto?

${\sf pref}(L)=\{w \mid \exists w', ww' \in L \}$

Alternativamente, ¿son los CSL cerrados bajo cociente con los lenguajes regulares?

También se apreciarán resultados similares para los CSL deterministas.

Answer 1

No. Considera el lenguaje $L_{\text{halts-in}}$ que contiene las palabras $\text{enc}(T) c^n$ tal que la máquina de Turing $T$ que utiliza un alfabeto binario de cinta se detiene exactamente en $n$ pasos en la entrada vacía. Aquí $\text{enc}$ es cualquier codificación razonable de tales máquinas en palabras sobre $\{a,b\}$ . Este lenguaje es determinista sensible al contexto ya que una máquina de Turing universal puede simular $n$ pasos de cualquier máquina binaria de Turing $T$ en el espacio lineal (dejo los detalles al lector). Por último, $\text{enc}(T) c \in \text{pref}(L_{\text{halts-in}})$ si y sólo si $T$ finalmente se detiene en la entrada vacía, que es incalculable, por lo que $\text{pref}(L_{\text{halts-in}})$ es un lenguaje no computable. En particular, no es sensible al contexto.