|
|
|
|
|
|
Now show that  and  . |
|
|
|
|
|
|
|
|
10-19 Give a proof of Proposition 10.47. |
|
|
|
|
|
|
|
|
Hint: Fix some integer m > 1. Let n0 = 0, and for each i and each j < i, let |
|
|
|
|
|
|
|
|
For each j, let  . Consider  , the class of languages  , each of which satisfies: |
|
|
|
|
|
|
|
|
1.  |
|
|
|
|
|
|
|
|
2.  |
|
|
|
|
|
|
|
|
3.  |
|
|
|
|
|
|
|
|
4.  |
|
|
|
|
|
|
|
|
5. is finite or co-finite. |
|
|
|
|
|
|
|
|
Show that  (first, use the additional information to construct a text for the complement of the input language; then use the identification method used to identify finite (respectively, co-finite) languages on characteristic function input). Also, observe that  , and  . Use this observation to argue that  . |
|
|
|
|
