What is the definition of ambiguity of context-sensitive
grammar?This is relevant to the definition of inherent ambiguity of
context-sensitive language.And any proof for the inherent ambiguity of the
language $L = {a^ib^ic^id^je^jf^j \bigcap a^ib^jc^id^je^if^j} $ or
$a^nb^nc^nd^ne^nf^n$?


Since another question about inherent ambiguity of the context-sensitive language leads to suspicion of definition of ambiguity of CSG and inherent ambiguity of the context-sensitive language,and has been closed and deleted,a thesis founded on web claims Inherent ambiguity of the context-sensitive language $L = {a^ib^ic^id^je^jf^j \bigcap a^ib^jc^id^je^if^j} $ or $a^nb^nc^nd^ne^nf^n$.Here come the two questions above.



Inherent ambiguity of the context-sensitive language $L = {a^ib^ic^id^je^jf^j \bigcap a^ib^jc^id^je^if^j} $ or $a^nb^nc^nd^ne^nf^n$
Let me define a context-sensitive language *strongly unambiguous* if it is recognizable by a context-sensitive grammar such that every string in the language has a *unique* derivation. (Note that in the CFL world, this condition is much stronger than plain unambiguity.)


I don’t know if there *is* a sensible well-behaved definition of an unambiguous context-sensitive language, but any *reasonable* such definition should have at least the property that every strongly unambiguous language is unambiguous. (The definition in Noah S’s answer violates this condition, so I do not consider it reasonable: it may well happen that a derivable string has no leftmost derivation at all, even if it has a unique derivation; for much the same reason, that definition also apparently violates another reasonable requirement, namely that the class of unambiguous CSL should be invariant under left-to-right reversal.)


As explained below in more detail, it follows that under any reasonable definition, the language given in the question is unambiguous. Furthermore, it is impossible to unconditionally prove that *any* context-sensitive language is inherently ambiguous without serious assumptions from computational complexity.


The class of context-sensitive languages is well-known to coincide with $\mathrm{NSPACE}(O(n))$, i.e., languages recognizable by a nondeterministic linear-space Turing machine. This contains the class of deterministic linear-space languages $\mathrm{DSPACE}(O(n))$. There is a natural notion of unambiguity used in this context (e.g., classes like UL or UP): a nondeterministic Turing machine is unambiguous if every string is accepted by at most one computation path. The class $\mathrm{USPACE}(O(n))$ of languages recognized by an unambiguous linear-space Turing machine is intermediate between the other two, that is,
$$\mathrm{DSPACE}(O(n))\subseteq\mathrm{USPACE}(O(n))\subseteq\mathrm{NSPACE}(O(n))=\mathrm{CSL}.$$
To put things into context, the closure of any of these classes under polynomial-time reductions is $\mathrm{PSPACE}$.


Now, the point is that the reduction of $\mathrm{NSPACE}(O(n))$ to CSL preserves the number of accepting paths: that is, given a nondeterministic linear-space Turing machine $M$, one can construct a context-sensitive grammar $G$ recognizing the same language in such a way that every $G$-derivation of a string $w$ corresponds to a unique accepting path of $M$ on input $w$, and vice versa. In particular, if $M$ is unambiguous, then $G$ is strongly unambiguous. So, the class of strongly unambiguous CSL languages (and a fortiori, unambiguous CSL languages under any reasonable definition) contains $\mathrm{USPACE}(O(n))$, and therefore $\mathrm{DSPACE}(O(n))$.


The language in the question can be recognized in a straightforward way by a deterministic logarithmic-space Turing machine, hence it is strongly unambiguous.


Moreover, the existence of any inherently ambiguous CSL language would imply a separation of $\mathrm{USPACE}(O(n))$ and $\mathrm{DSPACE}(O(n))$ from $\mathrm{NSPACE}(O(n))$, and by padding, also a separation of (U)L from NL. These are notoriously difficult open problem in complexity, akin to separation of P from NP.


Incidentally, since every CFL (or LOGCFL) language can be recognized in deterministic space $O((\log n)^2)$ (and quasi-polynomial time), this also shows that every *context-free* language is a strongly unambiguous *context-sensitive* language. Given that one might reasonably demand the opposite, this suggests that there is in fact no reasonable definition of unambiguous CSL.


