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

• 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 – Marzio De Biasi Jun 28 '14 at 21:13
• hopcroft ullman state paraphrased "almost any algorithm one can think of is CSL" and apparently all known nonCSLs are "contrived" – vzn Jun 29 '14 at 17:06
• @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) – Marzio De Biasi Jun 30 '14 at 23:36
• This doesn't seem to be a research-level question. – David Richerby Jul 1 '14 at 6:22
• @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 Jul 1 '14 at 11:42

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