Can someone give a simple but non-toy example of a context-sensitive grammar?

Problem Detail: 

I'm trying to understand context-sensitive grammars.

I understand why languages like

1. $\{ww \mid w \in A^*\}$
2. $\{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?

Asked By : BlueBomber

Answered By : Hendrik Jan

Yes, I would believe this to be possible, but no I am not willing to explicitly construct that context-sensitive grammar. I will explain my answer, by splitting the question in two different parts.

(1) What would the non-toy example be? It should reflect declaration of variables. My proposal of such a language, abstracted from real programming would be something like this. The alphabet is $\{a,b,;,(,)\}$. $$\{ w_1;w_2;\dots;w_n(x_1;x_2;\dots;x_m) \mid w_i,x_j\in\{a,b\}^*, \mbox{ each }x_j\mbox{ is equal to some }w_i \} $$ That language is context-sensitive.

(2) To show it actually is context-sensitive I would use another formalism. That of a Turing machine with linear use of its tape: a linear bounded automaton LBA. I can program it to do the pattern matching/ I would consecutively consider each $x_j$ and try to match it with a proper $w_j$, letter by letter. LBA's are equivalent to context-sensitive grammars, but much easier to program.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7716