5. The solution here is reminiscent of the use of messengers with contextsensitive grammars.
8. While in principle each symbol has to be rewritten at each step, this can be
circumvented by a → a. Therefore, we can rewrite so that in each step a
single a is added, giving the language L(aa * ).
Chapter 14
Section 14.1
3. The choice of algorithm is important in sorting. Simple methods, such as the
bubblesort, have time-complexity O(n 2 ). The most efficient sorting
algorithms have time-complexity O(nlogn).
Section 14.2
4.
.
7. If one configuration grows, the information on the tape has to be moved.
Suppose a right shift has to be made. Go to the right end of the tape and
move every symbol in the active area one cell to the right. This takes O(nk n )
moves. If every one of the k n configurations grows in a single move, the
complete process requires O(n 3 k 2n ) moves. Since this is dominated by
O(k 3n ), the conclusion of the theorem is unaffected.
Section 14.3
4. This is an immediate consequence of Theorem 14.4.
8. While in principle each symbol has to be rewritten at each step, this can be
circumvented by a → a. Therefore, we can rewrite so that in each step a
single a is added, giving the language L(aa * ).
Chapter 14
Section 14.1
3. The choice of algorithm is important in sorting. Simple methods, such as the
bubblesort, have time-complexity O(n 2 ). The most efficient sorting
algorithms have time-complexity O(nlogn).
Section 14.2
4.
.
7. If one configuration grows, the information on the tape has to be moved.
Suppose a right shift has to be made. Go to the right end of the tape and
move every symbol in the active area one cell to the right. This takes O(nk n )
moves. If every one of the k n configurations grows in a single move, the
complete process requires O(n 3 k 2n ) moves. Since this is dominated by
O(k 3n ), the conclusion of the theorem is unaffected.
Section 14.3
4. This is an immediate consequence of Theorem 14.4.