In Chapter 1 of Kenneth Slonneger and Barry L. Kurtz's Formal Syntax and Semantics of Programming Languages: A Laboratory Based Approach, an example of its production is given to illustrate the nature of context-sensitive grammar (page 3):

<thing> b ::= b <thing>

where <thing> is a non-terminal and b is a terminal.

I cannot see how this fits the form

$$αAβ → αγβ $$ (where $α$ and $β$ are strings, $A$ is a non-terminal and $γ$ is a non-empty string) for context-sensitive grammar unless the right hand side ends with $b$ as well:

<thing> b ::= b <thing> b

in which case we get $α=ε$, $β=b$ and $γ = b\; \text{<thing>}$.

Perhaps I haven't viewed it in the right angle? (Or is this a typo?)

  • $\begingroup$ Hint: $\alpha, \beta, \gamma$ are strings over what? $\endgroup$
    – Raphael
    Feb 16, 2016 at 23:55

1 Answer 1


First, they describe noncontracting grammars, and give an example: the one you are quoting.

Next, they write: equivalently, we can use a different restriction on grammars, and describe the context-sensitive grammars.

Chomsky proved the equivalence in 1963.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.