Natural examples of context-sensitive languages from practice I am looking for natural examples of context-sensitive languages from practice. For example, reasonable answers could include grammar syntax of a programming language, or encoding of certain properties of a program. In particular, please draw analogy from call-string-based context sensitive interprocedural dataflow analysis where the matching parentheses context-free language is used to encode the matching of calls and returns. That is an example where context-free language is useful in practice, or at least to explain a practical problem in a nice little theoretical way. Now, how can a context-sensitive language be useful in a similar context/scenario? That is my question.

Please note that I am not looking for artificial encoding into CSL (made up just to answer this question).
There are two ways your question can be interpreted: the complexity
theorist view and the application programmer view, which is a bit caricaturing the
situation, but should get my meaning across.

People in complexity theory will mainly wonder whether an actual
problem, practical or theoretical, can be encoded into CSL
recognition.  As noted in the comments of Marzio De Biasi and of user
vzn, a large number of real world problems may be encoded as CSL, as
CSL are recognized by non-deterministic linear bounded automata (LBA), and
conversely . It means that all these algorithms belong to the powerful
class of problems solvable non-deterministically in linear space.

But I strongly doubt that a single one of them is actually solved in
this way for practical purposes. Which brings us to the other view.  I
guess everyone knows that context-free (CF) or regular languages are
used as theoretically defined for various purposes, such as the syntax
of programming languages, or string pattern matching. Since it is also
known that CF and regular languages are context-sensitive languages
(CSL), they do stand as excellent answer to the question.

But since you must have known that, I must conclude that this is not
the answer you were looking for. And the alternative is a more
restrictive question: whether the theoretical formalisation of CSL is
actually used as such for some "real-world" purpose.

Actual use of a formalism in the real world usually entails 2
properties:


the formalism must be perspicuous, and express appropriately the
structural properties of the problem for which it is used.
the formalism must be computationally tractable (in a pragmatic sense).


My impression is that neither is an obvious characteristic of CS
languages. I am no expert on this, and you should not trust me too
much, but there does not seem to be structural organisation that can
be associated to all CSL, like parse-trees can be associated to
strings of CFL, or like regular expressions, even though many closure
properties are known for CSL (which are AFLs). Also, the associated
automaton, the LBA, is not the most obvious computing device to use as it is
non deterministic, and probably too powerful to be simulated
efficiently in specific application. But I insist this is just informal
intuition, not hard facts.

The fact is that many problems, like CF and regular languages, do not
need the full power of CSL and can be better dealt with more
specialized formalism, computationally easier to use, and expressing
more closely the problem at hand.

A typical example is in natural language processing. There are
linguistics structures (such as cross-serial dependency) that are not
naturally expressed with CF languages. Thus scientists have been
defining more powerful syntactics formalisms, such as tree-adjoining
grammar (TAG), Combinatory categorial grammars, ..., and the whole hierarchy
of linear context-free rewriting system (LCFRS), sometimes called
collectively mildly context-sensitive languages.

Another way to venture into context-sensitivity is to use a
context-free backbone and attach to the non-terminals various
attributes that must satisfy equations associated with rules.  This
lead to the attribute grammar formalism in compiler technology, and to
the use of so called feature structures in formalisms like lexical functional
grammar.

In other word, people do venture in the realm of context sensitivity,
but with specialized formalisms that are well adapted for expressing
the problems adressed. Actually, the two form of venturing into
context sensitivity described above can be combined and are combined.

Natural and programming languages are not the only application. For
example TAGs and equivalent formalism have been considered in biology
the explain DNA structures related to specific types of folding of DNA or RNA strands.

So the answer is yes, context-sensitivity is used, both in the
complexity sense and in real applications.  But no, it is not, as far
as I know, by direct use of the CSL formalism.



Note: Marzio De Biasi pointed to a genetics article that claims to
use a context sensitive grammar.  This is probably to be taken
informally as "more powerful than context-free". Indeed, the claim
later concerns "a context-sensitive deterministic grammar", which is
both undefined and significantly restrictive. Later description shows
that it seems actually a minimal extension of CFL, probably less powerful
than the use of TAGs (but I would need more work to see precisely
where it stands: it may just be CF in power).