Problem Detail: I’m trying to understand context-sensitive grammars. I understand why languages like
- ${ww mid w in A^*}$
- ${a^n b^n c^n mid ninmathbb{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_jin{a,b}^*, mbox{ each }x_jmbox{ 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
