snippetMinor
How to make sense of this context-sensitive production in a textbook? (a typo perhaps?)
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):
where `
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:
in which case we get $α=ε$, $β=b$ and $γ = b\; \text{}$.
Perhaps I haven't viewed it in the right angle? (Or is this a typo?)
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 bin 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.
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.