snippetModerate
Can someone give a simple but non-toy example of a context-sensitive grammar?
Viewed 0 times
toycansimplenonexamplesomeonebutgivegrammarcontext
Problem
I'm trying to understand context-sensitive grammars.
I understand why languages like
are not context free, but what I'd like to know if a language similar to the untyped lambda calculus is context sensitive.
I'd like to see an example of a simple, but non-toy (I consider the above toy examples), example of a context-sensitive grammar that can, for some production rule, e.g., tell whether or not some string of symbols is in scope currently (e.g. when producing the body of a function).
Are context sensitive grammars powerful enough to make undefined/undeclared/unbound variables a syntactic (rather than semantic) error?
I understand why languages like
- $\{ww \mid w \in A^*\}$
- $\{a^n b^n c^n \mid n\in\mathbb{N}\}$
are not context free, but what I'd like to know if a language similar to the untyped lambda calculus is context sensitive.
I'd like to see an example of a simple, but non-toy (I consider the above toy examples), example of a context-sensitive grammar that can, for some production rule, e.g., tell whether or not some string of symbols is in scope currently (e.g. when producing the body of a function).
Are context sensitive grammars powerful enough to make undefined/undeclared/unbound variables a syntactic (rather than semantic) error?
Solution
My favourite example of a context-sensitive language (CSL) is SAT. The Landweber-Kuroda Theorem says that CSL = NSPACE$[n]$. Any SAT instance has a linear-size certificate, so SAT is a CSL. See my question Context-sensitive grammar for SAT? for references and discussion.
Many other NP-hard languages are also in CSL by the same reason, such as CLIQUE.
There are also fairly natural languages in CSL that are even harder.
However, I am not aware of any way to express an arbitrary CSL as a context-sensitive grammar (CSG), other than to use Landweber's construction in Theorem 3 of his paper. In this construction, the CSG describes the reverse of the operation of the linear-bounded automaton that recognizes the CSL. Productions of the CSG describe how a particular state of the machine results from one possible move. Such a CSG is straightforward translation of the automaton into a grammar, so it is not necessarily going to correspond to language features such as being able to declare variables, but will instead be bogged down by the details of the automaton.
If you insist on a CSG rather than a CSL, and if your actual question is specifically about wanting to see a CSG for a language that involves restricted variable scoping, then Hendrik Jan's answer seems to be a good start.
Many other NP-hard languages are also in CSL by the same reason, such as CLIQUE.
There are also fairly natural languages in CSL that are even harder.
However, I am not aware of any way to express an arbitrary CSL as a context-sensitive grammar (CSG), other than to use Landweber's construction in Theorem 3 of his paper. In this construction, the CSG describes the reverse of the operation of the linear-bounded automaton that recognizes the CSL. Productions of the CSG describe how a particular state of the machine results from one possible move. Such a CSG is straightforward translation of the automaton into a grammar, so it is not necessarily going to correspond to language features such as being able to declare variables, but will instead be bogged down by the details of the automaton.
If you insist on a CSG rather than a CSL, and if your actual question is specifically about wanting to see a CSG for a language that involves restricted variable scoping, then Hendrik Jan's answer seems to be a good start.
Context
StackExchange Computer Science Q#7716, answer score: 16
Revisions (0)
No revisions yet.