Here is another grammar/machine problem reduction that is pretty straightforward.
The problem: Context-Sensitive Language Membership. This is problem AL20 in the appendix.
The description: Given a context-sensitive grammar G = (N, Σ, ∏, S) and a string w from Σ*. Is w in the language generated by G?
Example: Lots of these grammars are complicated because you need to do some crazy productions to make it worth using the context-sensitiveness of the grammar (as opposed to just being a “regular” context-free grammar). But Martin’s Theory of Computation book has a pretty nice one for the language anbncn:
So, if we wanted the string aabbcc we could do:
S->SABC ->ABCABC ->ABACBC->AABCBC ->AABBCC->aABBCC->aaBBCC->aabBCC->aabbCC->aabbcC->aabbcc
So if we were handed this grammar and any string of the form anbncn, we should get a “yes” response. If we had any other string, we would get a “no” response.
Reduction: Since we know that Linear Bounded Automata are the machines that accept context-sensitive grammars, it seems straightforward to go from Linear Bounded Automaton Acceptance. The good news is that the equivalence proofs that are used to show that Linear Bounded Automata and Context-Sensitive grammars are equivalent (for example, theorems 8.14 and 8.20 in Martin’s Theory book) build grammars from machines in polynomial time. So our reduction can just be to take an LBA machine and a string, build the equivalent grammar (in polynomial time) and we have an equivalent context-sensitive grammar.
Difficulty: 4. The hard part is convincing yourself that the conversion algorithm really is polynomial. That’s not the sort of thing the theory books tend to worry about. (Heck, context-sensitive languages in general are skipped over in most theory of computation classes). But it’s a pretty easy consequence of the proof if you’re doing the proof in class anyway.