HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to make sense of this context-sensitive production in a textbook? (a typo perhaps?)

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thisproductiontypomakeperhapssensetextbookhowcontextsensitive

Problem

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):

 b ::= b 


where ` 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:

 b ::= b  b


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

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

Solution

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.

Context

StackExchange Computer Science Q#53208, answer score: 6

Revisions (0)

No revisions yet.