[next] [prev] [prev-tail] [tail] [up]

 Exercises

  
4.1.1
Let M be the Turing transducer whose transition diagram is given in Figure 4.1.3. Give the sequence of moves between configurations that M has on input baba.  
4.1.2
For each of the following relations construct a Turing transducer that computes the relation.
  1.  { (aibici, di) | i >= 0 }
  2.  { (x, di) | x is in {a, b, c}* and i = (the number of a's in x) = (the number of b's in x) = (the number of c's in x) }
  3.  { (x, di) | x is in {a, b, c}* and i = min(number of a's in x, number of b's in x, number of c's in x) }
  4.  { (xxrevy, ai) | x and y are in {a, b}*, and i = (number of a's in x) = (number of a's in y) }
  5.  { (ai, bj) | j >= i2 }
 
4.1.3
For each of the following languages construct a Turing machine that recognizes the language.
  1.  { xyx | x and y are in {a, b}* and |x| >= 1 }
  2.  { xy | xy is in {a, b, c}*, |x| = |y|, and (the number of a's in x) = (the number of a's in y) }
  3.  { xy | xy is in {a, b, c}*, |x| = |y|, and (the number of a's in x) /= (the number of a's in y) }
  4.  { aixbi | x is in {a, b}*, and i = (the number of a's in x) = (the number of b's in x) }
  5.  { aibicjdj | i/= j }
  6.  { aba2b2a3b3 . . . anbn | n >= 0 }

 

4.1.4
Show that the relations computable by Turing transducers are closed under the following operations .
  1.  Union.
  2.  Intersection.
  3.  Reversal, that is, the operation that for a given relation R provides the relation { (xrev, yrev) | (x, y) is in R }.
 
4.1.5
Show that recursive languages are closed under complementation. (The result does not carry over to recursively enumerable languages because the language Ldiagonal_reject, as defined in Section 4.5, is not a recursively enumerable language, whereas its complementation is.)  
4.1.6
Show that each linear bounded automaton has an equivalent linear bounded automaton that halts on all inputs.  
4.1.7
Show that each Turing transducer has an equivalent three-states Turing transducer.   
4.2.1
Redo Example 4.2.1 for the case that P has the instructions of Figure 4.E.1.
  
do
    y := y + 1
or
    if x = y then
        if eof then accept
    read x
    write x
until false
 
Figure 4.E.1
 
4.2.2
Find the values of dstate(q2, ˘, B, B), dc1(q2, ˘, B, B), dc2(q2, ˘, B, B), dd0(q2, ˘, B, B), dd1(q2, ˘, B, B), dd2(q2, ˘, B, B), and dr(q2, ˘, B, B) in Figure 4.2.5(b) for the case that M is the deterministic Turing transducer in Figure 4.1.6.  
4.2.3
Find the values of dtran(q2, a, B, q2, 0, B, +1, e) and dtran(q3, a, b, q3, +1, a, +1, e) in Figure 4.2.5(c) for the case that M is the nondeterministic Turing transducer in Figure 4.1.3.  
4.2.4
For each of the following cases determine the value of the corresponding item according to Example 4.2.4.
  1.  The natural number that represents the string BBBccc.
  2.  The string represented by the natural number 21344.
  
4.3.1
Find the transition diagram of M2 in Example 4.3.1 for the case that M1 is the Turing transducer of Figure 4.E.2.
   
[PICT]
Figure 4.E.2
 
4.3.2
Show that each deterministic, two auxiliary-work-tape Turing transducer M1 has an equivalent deterministic, one auxiliary-work-tape Turing transducer M2.   
4.4.1
Find a standard binary representation for the Turing transducer whose transition diagram is given in Figure 4.E.2.  
4.4.2
Let M be a Turing transducer whose standard binary representation is the string 01401012014001201401401400101201500130140012001013014014013014014 012001013013014014013001301401.
  1.  How many accepting states does M have?
  2.  How many transition rules does M have?
  3.  How many transition rules of M provide a nonempty output?
  4.  How many auxiliary work tapes does M have?
 
4.4.3
For each of the following strings either give a Turing transducer whose standard binary representation is equal to the string, or justify why the string is not a standard binary representation of any Turing transducer.
  1.  01101011000110111101101111
  2.  0140101201400120140140140140101201500130130012001013015014012014 001300101201300140130013001
  3.  0140101201400120140140140140101201500130130012001013015013012014 00130010120130014013013001
  
4.5.1
Discuss the appropriateness of the following languages as a replacement for the language Ldiagonal_reject in the proof of Theorem 4.5.1.
  1.  { x | x = xi, and Mi+2 does not accept xi }.
  2.  { x | x = xi, and M |~ i/2 ~| does not accept xi }.
  3.  { x | x = xi, and either M2i-1 does not accept xi or M2i does not accept xi }.
 
4.5.2
The proof of Theorem 4.5.1 uses the diagonal of the table Taccept to find the language Ldiagonal_reject that is accepted by no Turing machine. Show that besides the diagonal, there are infinitely many other ways to derive a language from Taccept that is accepted by no Turing machine.  
4.5.3
Use a proof by diagonalization to show that there is an undecidable membership problem for a unary language.  
4.5.4
What is M oo in the proof of Theorem 4.5.5 if M is the Turing machine given in Figure 4.E.3?
   
[PICT]
Figure 4.E.3
 
4.5.5
Find a Turing machine Mx that satisfies the conditions in the proof of Theorem 4.5.6 if M is the Turing machine in Figure 4.E.3 and x = abb.  
4.5.6
Show that no linear bounded automaton can accept LLBA_reject = { x | x = xi and Mi does not have an accepting computation on input xi in which at most |xi| locations are visited in each auxiliary work tape }.  
4.5.7
Use the undecidability of the membership problem for Turing machines to show the undecidability of the following problems for Turing machines.
  1.  The problem defined by the following domain and question.
    Domain:
    { (M, x, p) | M is a Turing machine, p is a state of M, and x is an input for M }.
    Question:
    Does M reach state p on input x, for the given instance (M, x, p)?
  2.  Empty-word membership problem.
  3.  Uniform halting problem.
  4.  Emptiness problem.
  5.  Equivalence problem.
If the Turing machine M is as in Figure 4.5.6(a) and x = ababc, then what is the corresponding instance implied by your reduction for each of the problems in (a) through (e)?  
4.5.8
Show that the nonacceptance problem for Turing machines is not partially decidable.   
4.6.1
Let G be the grammar whose production rules are listed below. 

   S  -->   aSSb
     -->   e
abS  -->   bSaS

Find a Turing machine MG, in accordance with the proof of Theorem 4.6.1, that accepts L(G).  

4.6.2
Let M be the Turing machine whose transition diagram is given in Figure 4.E.4.
   
[PICT]
Figure 4.E.4
Use the construction in the proof of Theorem 4.6.2 to obtain a grammar that generates L(M). 
4.6.3
For each of the following languages find a context-sensitive grammar that generates the language.
  1.  { aibici | i >= 0 }
  2.  { aibjcjdj | i/= j }
  3.  { xx | x is in {a, b}* }
 
4.6.4
Show that a language is Type 1 if and only if it is a context-sensitive language.  
4.6.5
Show, by refining the proofs of Theorem 4.6.1 and Theorem 4.6.2, that a language is Type 1 if and only if it is accepted by a linear bounded automaton.   
4.7.1
Solve the PCP problem for each of the following instances (and justify your solutions).
  1.  <(115, 13), (117, 18), (112, 129)>
  2.  <(1, 10), (10, 01), (0, 011), (100, 01)>
  3.  <(0100, 01), (10, 0), (1, 10)>
 
4.7.2
Show that PCP is decidable when the strings are over a unary alphabet.  
4.7.3
Let G be the grammar whose production rules are 

 S  -->   aSSa
   -->   Sb
   -->   e

Find the instance of PCP that corresponds to the instance (G, aba), as determined by the proof of Theorem 4.7.1.  

4.7.4
Find the finite-state transducers M1 and M2 in the proof of Corollary 4.7.1 for the instance <(ab, a), (a, ba)> of PCP.  
4.7.5
Find the pushdown automata M1 and M2 in the proof of Corollary 4.7.2 for the instance <(ab, a), (a, ba)> of PCP.  
4.7.6
Show, by reduction from PCP, that the ambiguity problem is undecidable for finite-state transducers and for pushdown automata.

[next] [prev] [prev-tail] [front] [up]