HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Closure of context-sensitive languages under inverse language substitution

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
inversesubstitutionlanguageslanguageundercontextsensitiveclosure

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#140873, answer score: 3

Revisions (0)

No revisions yet.