use the construction in Theorem 7.1. The pda we get from this consumes one
input symbol on every move and never increases the stack contents by more
than one symbol each time.
Chapter 11
Section 11.1
2. We know that the union of two countable sets is countable and that the set of
all recursively enumerable languages is countable. If the set of all languages
that are not recursively enumerable were also countable, then the set of all
languages would be countable. But this is not the case, as we know.
6. Let L 1 and L 2 be two recursively enumerable languages and M 1 and M 2 be the
respective Turing machines that accept these two languages. When
represented with an input w, we nondeterministically choose M 1 or M 2 to
process w. The resultis a Turing machine that accepts L 1 ∪ L 2 .
11. A context-free language is recursive, so by Theorem 11.4 its complement is
also recursive. Note, however, that the complement is not necessarily
context-free.
14. For any given w ∈ L + , consider all splits w = w 1 w 2 …w m . For each split,
determine whether or not w i ∈ L. Since for each w there are only a finite
number of splits, we can decide whether or not w ∈ L + .
18. The argument attempting to show by diagonalization that 2 s is not
countable for finite S fails because the table in Figure 11.2 is not square,
having |2 s | rows and |S| columns.
input symbol on every move and never increases the stack contents by more
than one symbol each time.
Chapter 11
Section 11.1
2. We know that the union of two countable sets is countable and that the set of
all recursively enumerable languages is countable. If the set of all languages
that are not recursively enumerable were also countable, then the set of all
languages would be countable. But this is not the case, as we know.
6. Let L 1 and L 2 be two recursively enumerable languages and M 1 and M 2 be the
respective Turing machines that accept these two languages. When
represented with an input w, we nondeterministically choose M 1 or M 2 to
process w. The resultis a Turing machine that accepts L 1 ∪ L 2 .
11. A context-free language is recursive, so by Theorem 11.4 its complement is
also recursive. Note, however, that the complement is not necessarily
context-free.
14. For any given w ∈ L + , consider all splits w = w 1 w 2 …w m . For each split,
determine whether or not w i ∈ L. Since for each w there are only a finite
number of splits, we can decide whether or not w ∈ L + .
18. The argument attempting to show by diagonalization that 2 s is not
countable for finite S fails because the table in Figure 11.2 is not square,
having |2 s | rows and |S| columns.