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.  { (aⁱbⁱcⁱ, dⁱ) | i 0 }
2.  { (x, dⁱ) | 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, dⁱ) | 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.  { (xx^revy, aⁱ) | x and y are in {a, b}*, and i = (number of a's in x) = (number of a's in y) }
5.  { (aⁱ, b^j) | j i² }

 

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.  { aⁱxbⁱ | x is in {a, b}*, and i = (the number of a's in x) = (the number of b's in x) }
5.  { aⁱbⁱc^jd^j | i j }
6.  { aba²b²a³b³ aⁿbⁿ | 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 { (x^rev, y^rev) | (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 L_{diagonal_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 _state(q₂, ¢, B, B), _c1(q₂, ¢, B, B), _c2(q₂, ¢, B, B), _d0(q₂, ¢, B, B), _d1(q₂, ¢, B, B), _d2(q₂, ¢, B, B), and (q₂, ¢, 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 _tran(q₂, a, B, q₂, 0, B, +1, ) and _tran(q₃, a, b, q₃, +1, a, +1, ) 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 M₂ in Example 4.3.1 for the case that M₁ is the Turing transducer of Figure 4.E.2.

---

Figure 4.E.2

---

 

4.3.2

Show that each deterministic, two auxiliary-work-tape Turing transducer M₁ has an equivalent deterministic, one auxiliary-work-tape Turing transducer M₂.   

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 01⁴0101²01⁴001²01⁴01⁴01⁴00101²01⁵001³01⁴001²00101³01⁴01⁴01³01⁴01⁴ 01²00101³01³01⁴01⁴01³001³01⁴01.

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.  01⁴0101²01⁴001²01⁴01⁴01⁴01⁴0101²01⁵001³01³001²00101³01⁵01⁴01²01⁴ 001³00101²01³001⁴01³001³001
3.  01⁴0101²01⁴001²01⁴01⁴01⁴01⁴0101²01⁵001³01³001²00101³01⁵01³01²01⁴ 001³00101²01³001⁴01³01³001

  

4.5.1

Discuss the appropriateness of the following languages as a replacement for the language L_{diagonal_reject} in the proof of Theorem 4.5.1.

1.  { x | x = x_i, and M_i+2 does not accept x_i }.
2.  { x | x = x_i, and M_i/2 does not accept x_i }.
3.  { x | x = x_i, and either M_2i-1 does not accept x_i or M_2i does not accept x_i }.

 

4.5.2

The proof of Theorem 4.5.1 uses the diagonal of the table T_accept to find the language L_{diagonal_reject} that is accepted by no Turing machine. Show that besides the diagonal, there are infinitely many other ways to derive a language from T_accept 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 in the proof of Theorem 4.5.5 if M is the Turing machine given in Figure 4.E.3?

---

Figure 4.E.3

---

 

4.5.5

Find a Turing machine M_x 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 L_{LBA_reject} = { x | x = x_i and M_i does not have an accepting computation on input x_i in which at most |x_i| 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.

Find a Turing machine M_G, 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.

---

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.  { aⁱbⁱcⁱ | i 0 }
2.  { aⁱb^jc^jd^j | 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.  <(1¹⁵, 1³), (1¹⁷, 1⁸), (1¹², 1²⁹)>
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

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 M₁ and M₂ in the proof of Corollary 4.7.1 for the instance <(ab, a), (a, ba)> of PCP.  

4.7.5

Find the pushdown automata M₁ and M₂ 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]