Theorem 7.1.2: each non-erasing general phrase structure grammar is equivalent to a context-sensitive grammar.
Example 7.1.1.
A non-erasing grammar for {a2k | k0} (start = S).
S _ DS | A, DA _ aA, A _ a,
Da _ aaD.
As a sample derivation we have:
S _ DS _ DDS _ DDA _ DaA _ aaDA _ aaaA _ a4
In general, S _* Dk A _* a2k
Previous slide | Next slide | Back to first slide | View graphic version |