We define language substitution for a Context-Sensitive Language (CSL) $S$ over an alphabet $\Sigma$ is a map from $\Sigma$ into CSL's, for example: $f(abc) = L_1(a) L_2(b) L_3(c)$ such that (I guess) the union of all $L(s)$ for $s \in f(S)$ is defined to be $L(f(S))$ and $L(f(S))$ is known to be a CSL itself.

That is my interpretation of language substitution for CSL's. Well languages are also closed under inverse of string homomorphisms, homomorphisms $f$ being a special case of language substitution in which each $a \in \Sigma$ gets mapped to a singleton language $L_1(a) = \{f(a)\}$.

So my question is simple, yet probably hard or interesting to prove. That is, are CSL's closed under inverse of language substitution? Wikipedia is silent on this topic.

Let $f$ be a language substitution taking $S$ to $f(S)$. Then $f^{-1}(S) := \bigcup f^{-1}(s)$ I'm assuming. Is that a CSL?


1 Answer 1


Fix a universal Turing machine $T$.

Let $L_1$ be the language of all sequences of configurations $c_1 \# c_2 \# \cdots \# c_\ell$ which describe a valid computation of $T$, starting with an arbitrary initial configuration $c_1 \neq \epsilon$, and ending with a halting state; we do not allow any further configurations to appear. This language is clearly context-sensitive (it can be accepted in linear space even deterministically).

Let $L_2$ be the language of all sequences of configurations $c_1 \# c_1 \# c_2 \# \cdots \# c_\ell$ such that $c_1 \# c_2 \# \cdots \# c_\ell \in L_1$ (notice the initial configuration is repeated twice). This language is also context-sensitive.

Define a function $f$ from $\Sigma$ to CSLs by $f(\sigma) = \{ \sigma \}$ for $\sigma \neq \#$ and $f(\#) = \{ \#w : w \in L_1 \}$.

Notice that $f^{-1}(L_2)$ consists of strings $c_1\#$, where $c_1$ is an initial configuration of $T$ on which $T$ eventually halts. Thus $f^{-1}(L_2)$ is not computable.

  • 1
    $\begingroup$ It seems we can as well take $f(\#) = \{\#w \mid w\in C\}$ where $C$ is a (regular!) set of sequences of configurations, not necessarily forming a valid computation. I assume that the initial $c_1\#$ is over a different alphabet than $C$. Now again $f^{-1}(L_2)$ consists of strings $c_1\#$ for which there exists a valid computation, since $f$ must be able to assign a string in $L_2$. If correct, that would mean even inverse regular substitutions lead out of context-sensitive. $\endgroup$ Commented Jun 3, 2021 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.