patternMinor
Closure of context-sensitive languages under inverse language substitution
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?
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.
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.