The equivalence argument is straightforward.
Section 11.3
1. (c) Working with context-sensitive grammars is not always easy. The idea
of a messenger, introduced in Example 11.2, is often useful. In this
problem, the first step is to create the sentential form a n Bc n D. The
variables B and D will actas markers and messengers to assure that the
correct number of b's and d's are created in the right places. The first
part is achieved easily with the productions
In the next step, the B travels to the right to meet the D, by
When that happens, we can create one d and a return messenger that will
put the b in the right place and stop.
Alternatively, we create a d plus a marker D, with a different messenger that
creates a b, but keeps the process going:
4. The easiest argument is from an lba. Suppose that a language is contextsensitive. Then there exists an lba M that accepts it. Given w, we first rewrite
it as w R , then apply M to it. Because L R = {w : w R ∈ L}, M accepts w R if and
Section 11.3
1. (c) Working with context-sensitive grammars is not always easy. The idea
of a messenger, introduced in Example 11.2, is often useful. In this
problem, the first step is to create the sentential form a n Bc n D. The
variables B and D will actas markers and messengers to assure that the
correct number of b's and d's are created in the right places. The first
part is achieved easily with the productions
In the next step, the B travels to the right to meet the D, by
When that happens, we can create one d and a return messenger that will
put the b in the right place and stop.
Alternatively, we create a d plus a marker D, with a different messenger that
creates a b, but keeps the process going:
4. The easiest argument is from an lba. Suppose that a language is contextsensitive. Then there exists an lba M that accepts it. Given w, we first rewrite
it as w R , then apply M to it. Because L R = {w : w R ∈ L}, M accepts w R if and