<p>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.</p>

<p>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 <a href="https://cstheory.stackexchange.com/posts/comments/62353">Marzio De Biasi</a> and of <a href="https://cstheory.stackexchange.com/posts/comments/62376">user
vzn</a>, 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.</p>

<p>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.</p>

<p>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.</p>

<p>Actual use of a formalism in the real world usually entails 2
properties:</p>

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

<p>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 <a href="http://en.wikipedia.org/wiki/Abstract_family_of_languages" rel="nofollow noreferrer">AFL</a>s). 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.</p>

<p>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.</p>

<p>A typical example is in natural language processing. There are
linguistics structures (such as <a href="https://linguistics.stackexchange.com/questions/414">cross-serial dependency</a>) 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 <a href="http://en.wikipedia.org/wiki/Mildly_context-sensitive_language" rel="nofollow noreferrer">mildly context-sensitive languages</a>.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Attribute_grammar" rel="nofollow noreferrer">attribute grammar</a> formalism in compiler technology, and to
the use of so called <a href="http://en.wikipedia.org/wiki/Feature_structure" rel="nofollow noreferrer">feature structures</a> in formalisms like lexical functional
grammar.</p>

<p>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.</p>

<p>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 <a href="http://pstag.dna.bio.keio.ac.jp/" rel="nofollow noreferrer">folding of DNA or RNA strands</a>.</p>

<p>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.</p>

<hr>

<p>Note: Marzio De Biasi pointed to a <a href="http://www.biomedcentral.com/1471-2105/10/281" rel="nofollow noreferrer">genetics article</a> 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).</p>

CC BY-SA 3.0
2014-07-01T01:27:19.043Z
2014-07-01T01:27:19.043Z
2017-04-13T12:54:12.010Z
babou
<p>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.</p>

<p>Please note that I am not looking for artificial encoding into CSL (made up just to answer this question).</p>

CC BY-SA 3.0
2014-06-28T21:13:31.143Z
This should be quite "real-world" and also quite useful: $L=\{\varphi \mid \varphi \text{ is a CNF satisfiable formula} \}$ :-) ... more "standard" examples are programming languages; see: [context-sensitive analysis](https://www.cs.umd.edu/class/spring2006/cmsc430/lec6.2p.pdf)
Marzio De Biasi
CC BY-SA 3.0
2014-06-29T17:06:42.950Z
hopcroft ullman state paraphrased "almost any algorithm one can think of is CSL" and [apparently all known nonCSLs are "contrived"](http://cstheory.stackexchange.com/questions/11223/examples-of-non-csls-not-created-through-diagonalization)
vzn
CC BY-SA 3.0
2014-06-30T22:02:11.897Z
@MarzioDeBiasi These are abstract complexity answers. The fact is that CF and regular
languages (and a good collection of other formalisms) are actually
used as such, because the formalism is convenient and expressive for
various purposes such as pattern matching, syntactic backbones, error
processing, etc...  I do not know of any context, other than
theoretical, where CS languages are actually used.  I suspect that is
what the OP means by "real world".  Of course, many real world
problems can be encoded in a CS language, but it remains a theoretical
exercise, not a practical way to do things.
babou
CC BY-SA 3.0
2014-06-30T23:36:14.387Z
@babou: I must agree with you; even in natural language processing, CFGs are preferred, because the (few) linguistic phenomena cases in which CS languages are needed don't justify the exponential parsing time. I'm not an expert but perhaps something more "real" can be found in computational biology (e.g. something like [this](http://www.biomedcentral.com/1471-2105/10/281))
Marzio De Biasi
CC BY-SA 3.0
2014-07-01T06:22:14.310Z
This doesn't seem to be a research-level question.
David Richerby
CC BY-SA 3.0
2014-07-01T09:51:04.433Z
@MarzioDeBiasi I looked at the paper, cursorily. It seems that they use the qualificative CS very informally as: looking somewhat like CS, but not with the full power of CS. See note at the end of my answer. They do produce parse trees. They certainly do not use LBA.
babou
CC BY-SA 3.0
2014-07-01T11:42:25.290Z
@DavidRicherby Well, you may be right, but I am not sure. It may take
someone with wide knowledge to answer such a question positively, if
at all possible. And that could be interesting. Besides, I believe
that getting or disputing a proper vision of the role of concepts is
important, and possibly a major source of interesting breakthrough
... though it may not be the case here. I cannot help thinking of
Thomas Kuhn, possibly with considerable excess.
babou
CC BY-SA 3.0
2014-07-02T08:07:16.140Z
@babou It's the sort of thing that should be covered in any undergraduate textbook on formal languages. Research can be inspired by all kinds of things but that doesn't make those things on-topic here.
David Richerby
CC BY-SA 3.0
2014-07-02T11:10:40.623Z
@DavidRicherby I understand your point. But I am not so sure about
undergraduate texts. Else, some questions here, on CS or TCS, should
not even show up (including some that received fairly high upvotes).
Also, there is often disagreement over vision, as my former
(admittedly excessive) dispute over CF grammars meaning showed. Now
you may consider that TCS should be pure technicity, but that does
not seem to be the case. I also think that an original and useful
vision is as much a publishable result as a technical proof can be.
I guess this is more meta.
babou
<fl.formal-languages>
Natural examples of context-sensitive languages from practice
dacongy
# Natural examples of context-sensitive languages from practice

(Asked by: username_0 on 2014-06-28)

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).

**Tags:** fl.formal-languages
> **Comments:**
> **username_1**: This should be quite "real-world" and also quite useful: $L=\{\varphi \mid \varphi \text{ is a CNF satisfiable formula} \}$ :-) ... more "standard" examples are programming languages; see: [context-sensitive analysis](https://www.cs.umd.edu/class/spring2006/cmsc430/lec6.2p.pdf)  
> **username_2**: hopcroft ullman state paraphrased "almost any algorithm one can think of is CSL" and [apparently all known nonCSLs are "contrived"](http://cstheory.stackexchange.com/questions/11223/examples-of-non-csls-not-created-through-diagonalization)  
> **username_3**: @MarzioDeBiasi These are abstract complexity answers. The fact is that CF and regular languages (and a good collection of other formalisms) are actually used as such, because the formalism is convenient and expressive for various purposes such as pattern matching, syntactic backbones, error processing, etc...  I do not know of any context, other than theoretical, where CS languages are actually used.  I suspect that is what the OP means by "real world".  Of course, many real world problems can be encoded in a CS language, but it remains a theoretical exercise, not a practical way to do things.  
> **username_1**: @babou: I must agree with you; even in natural language processing, CFGs are preferred, because the (few) linguistic phenomena cases in which CS languages are needed don't justify the exponential parsing time. I'm not an expert but perhaps something more "real" can be found in computational biology (e.g. something like [this](http://www.biomedcentral.com/1471-2105/10/281))  
> **username_4**: This doesn't seem to be a research-level question.  
> **username_3**: @MarzioDeBiasi I looked at the paper, cursorily. It seems that they use the qualificative CS very informally as: looking somewhat like CS, but not with the full power of CS. See note at the end of my answer. They do produce parse trees. They certainly do not use LBA.  
> **username_3**: @DavidRicherby Well, you may be right, but I am not sure. It may take someone with wide knowledge to answer such a question positively, if at all possible. And that could be interesting. Besides, I believe that getting or disputing a proper vision of the role of concepts is important, and possibly a major source of interesting breakthrough ... though it may not be the case here. I cannot help thinking of Thomas Kuhn, possibly with considerable excess.  
> **username_4**: @babou It's the sort of thing that should be covered in any undergraduate textbook on formal languages. Research can be inspired by all kinds of things but that doesn't make those things on-topic here.  
> **username_3**: @DavidRicherby I understand your point. But I am not so sure about undergraduate texts. Else, some questions here, on CS or TCS, should not even show up (including some that received fairly high upvotes). Also, there is often disagreement over vision, as my former (admittedly excessive) dispute over CF grammars meaning showed. Now you may consider that TCS should be pure technicity, but that does not seem to be the case. I also think that an original and useful vision is as much a publishable result as a technical proof can be. I guess this is more meta.  

---

## 1 answers

### Answer by username_3 on 2014-07-01. Score: 10 | Accepted answer

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](https://cstheory.stackexchange.com/posts/comments/62353) and of [user
vzn](https://cstheory.stackexchange.com/posts/comments/62376), 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 [AFL](http://en.wikipedia.org/wiki/Abstract_family_of_languages)s). 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](https://linguistics.stackexchange.com/questions/414)) 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](http://en.wikipedia.org/wiki/Mildly_context-sensitive_language).

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](http://en.wikipedia.org/wiki/Attribute_grammar) formalism in compiler technology, and to
the use of so called [feature structures](http://en.wikipedia.org/wiki/Feature_structure) 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](http://pstag.dna.bio.keio.ac.jp/).

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](http://www.biomedcentral.com/1471-2105/10/281) 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).


---

