The Australian National University Semester 1, 2020 Research School of Computer Science Tutorial 6
Theory of Computation
This tutorial sheet contains way more exercises that you will be able to solve or discuss in the tutorial.
Exercise 1 TMs that recognise languages
Copyright By PowCoder代写 加微信 powcoder
For the following languages, construct a total Turing machine 1 that accepts precisely those strings. 1. {anbncn : n ≥ 1}
Y/Y,R a/a,R Z/Z,R Y/Y,R Y/Y,R a/X,R
B/B, R X/X, R b/Y, R
q5 q3 q2 c/Z,R
a/a, L Y/Y,L b/b, L Z/Z,L
b/b, R Z/Z,R
2. {ww:w∈{0,1}∗} Solution.
The solution I cane up with is quite complex, but the idea is to first replace 0 with A and 1 with B, working from the outside in. This allows us to find the middle. The next stage is to replace the last character of the first half with $, and replace the last character of the second half with # (if it matches). Repeat until there’s a non-matching character (which means the input is not of the form ww, and reject, or continue until the entire first half has been verified to be equal to the second half, and accept.)
1A Turing machine that halts for all inputs
A/A,R B/B,R Γ−Λ/Γ−Λ,R
A/A, L B/B, L
S0 R 0/A, R 1/B, R
1/1, L 0/0, L
0/A, L 1/B, L
B/B,S A/A,S
Γ−Λ/Γ−Λ,R end
erase $/$, L
Λ/Λ,L Γ−$/Γ−$,L reset Γ−$/Γ−$,L
Note that Γ − x/Γ − x, D is shorthand for “if the TM reads any symbol other than x from the tape,
write the same symbol back, and move in the D direction.” Exercise 2 Proving the language of a TM
Consider the following Turing machine M
ΛΛ Λ,R Λ,L
L 1 S1 Λ,L
0,1 0,R 1,R
1,0 1,L 0,L
Assume that the tape head starts pointing at the leftmost cell of the input. 1. Describe what this Turing machine does.
Solution. If the string is empty, it accepts. Otherwise, it deletes the left most zero (rejecting if one doesn’t exist), moves the tape head to the right, deletes the right most one (rejecting if one doesn’t exist), and rewind the tape back to the start. Repeat until tape is depleted.
2. What is the language L accepted by this Turing Machine? Solution.
L={0n1n :n≥0}
3. (hard) Prove that L = L(M), that is, formally prove that the language you described above actually
is the language recognized by the Turing machine.
We first need a few lemmas about the rewinding states R and L. ∗
Lemma 1 For any string α, β, βRα ⊢ βαR.
We prove by induction on α. Base case, α = ε. Trivially true, as βR ⊢ βR. Let β be arbitrary.
Assume true for some string α, prove true for xα, where x is a character. ∗
βRxα ⊢ βxRα ⊢ βxαR
where the first step is due to the definition of the TM, and the second step is the inductive hypothesis.
Lemma 2 For any string α, β, βLα ⊢ Lβα.
We prove by induction on β. Base case, β = ε. Trivially true, as Lα ⊢ Lα. Let α be arbitrary.
Assume true for some string β, prove true for βx, where x is a character. ∗
βxLα ⊢ βLxα ⊢ Lβxα
where the first step is due to the definition of the TM, and the second step is the inductive hypothesis.
Wefirstprovethatifw∈L,thenw∈L(M).Supposew∈L.Thenw=0n1n forsomen.Wewill prove by induction that w is always accepted.
Base case, n = 0.
So w = ε. The TM then directly follows the B transition and halts in an accepting state.
Assume that s00n1n ⊢ αFβ for some strings α,β ∈ Γ∗. Prove the same for w = 0n+11n+1. s00n+11n+1 ⊢ R0n1n+1
⊢ 0n1nS11 ⊢ 0n1n−1L1
⊢ S00n1n ∗
Hence we have by induction that w ∈ L ⇒ w ∈ L(M).
Now we need to prove w ∈ L(M) ⇒ w ∈ L.
Assume w ∈ L(M). Then w is accepted by the above Turing machine.
If w = ε then it is accepted and we are done. Assume w ̸= ε.
Clearly, w cannot start with a 1, as it would reject in S0. So w = 0α. Clearly, w cannot end in a 0, as otherwise w = 0β0, and
S0w = S00β0 ⊢ Rβ0 ⊢ β0R ⊢ βS10
which then rejects due to undefined transition. So then S0w = S00β1 ⊢ S0β, which means that we can repeat the same argument for β.
This gives us the recursive property P, defined as P(w) iff w = ε or w = 0β1, for some string β satisfying P(β), which provides a recursive definition of the set of all strings of the form 0n1n. Hence w ∈ L.
4. Prove that the Turing machine halts for all inputs, by constructing an upper bound on the number of transitions it can perform for an input of length n.
Solution. The Turing machine cannot infinitely loop on R, which fast forwards the tape to the first blank symbol on the right, or on L, which rewinds the tape to the first blank symbol on the left, as it would require infinitely many non-blank symbols, which is never possible. At most, when it enters state R (or L), it can spend no longer than n transitions there, where n is the original length of the input string.
The Turing machine also cannot visit S0 infinitely many times, as when it leaves, it either accepts in F (and halts), or it transitions to R, deleting a character from the string. (Note that no transition in the entire Turing machine overwrites a blank character with a non-blank, so the string can only get smaller.)
Combining these means that S0 must be visited at least once every 2n + 4 transitions (+4 for each edge on the square, +n for looping on R, and +n for looping on L), combined with the fact that each loop around the square deletes at least one character, means we have an upper bound of (2n + 4)n = O(n2) transitions before halting.2 Hence, the Turing machine can never run forever.
Exercise 3 Turing Machine Equivalence
We sometimes provide a Turing machine with extra capabilities (more symbols on the tape, more tapes, extra tape heads, ect.) as it makes designing them easier. This doesn’t actually give the Turing machine any additional expressiveness power, as we shall show.
Let T be the set of all Turing machines
(Q,Σ,Γ,δ,q0,B,F)
where Σ = {0,1}, Γ = {0,1,B} and δ : Q×Γ → Q×Γ×{L,R} is a partial function (δ may be undefined
for some inputs).
That is, T are all Turing machines for which the alphabet is just {0, 1}, the only tape symbols are {0, 1, B} where B is the blank symbol. In each state, the TM must read a symbol from the tape, write a symbol back, and move left or right.
Show that the following modifications do not change the expressive power of the Turing machine. That is, for each of the following families of Turing machines, describe how you can convert back and forth from the given class of machines to T -machines without changing the accepted language.
1. An S-machine is T-machine, but the transition function is of the form δ : Q × Γ → Q × Γ × {L, R, S}
The direction S (stay) does not move move the tape head after writing a symbol back to the tape. 2This is a rather weak upper bound.
Solution. It is clear that all T-machines are S-machines.
For each transition of the form δ(q, x) = (p, y, S) add a new dummy state rq,x,p,y,S , and define the
new transition function as
δ′(q,x) = (rq,x,p,y,S,y,R) if δ(q,x) = (p,y,S)
δ′(q, x) = δ(q, x) otherwise δ′(rq,x,p,y,S,z) = (p,z,L)
That is, the new transition function will do the same action as before in state q, but will move the tape head right, and transition to a dummy state rq,x,p,y,S. When the Turing machine is in this state, it reads the tape, writes the same symbol back, moves the tape head left, and transitions to p. A new dummy state to allow a move right, then a move left, essentially emulates not moving the tape head.
2. An F-machine is a T-machine with only one final state. Solution.
All F-machines are already T machines. For the other direction, note that a string is accepted as soon as a final state has been reached. In other words, whether or not there are outoing transitions from final states is irrelevant.
That means, we can convert a T-machine into an F-machine by • remove all outgoing transitions from final states
• merge all final states into one, keepign ingoing transitions
if the machine has at least one final state. Removal of the outgoing transitions in particular ensures
that the machine remains deterministic.
If the machine does not have any final states, we simply add a final state, without any transitions.
3. An O-machine is a T -machine, but the transition function is a total function (defined for all inputs). Solution. We add a sink state s with transitions δ(s, x) = (s, x, L) for all x ∈ Σ, and add transitions
δ(p, x) = (s, x, L) whenever δ(p, x)) is undefined.
In other words, if the T -machine rejects because of getting stuck in a non-final state, the O-machine
rejects because it gets stuck in an infinite loop (which does not visit a final state).
Exercise 4 Do we really need blank symbols?
Consider the family of psuedo-Turing machines P, with no reserved blank symbol. The alphabet and tape symbols are both the set {0, 1}. When the TM is given an input, the string is placed on the tape, and surrounded by infinitely many zeros on both sides. The tape head is placed on the leftmost bit of the input.
Notwithstanding the added complexity this presents to designing programs without blank symbols, it proves an issue for being able to tell where the input string ends (as there’d be no way to distinguish the string 100 from 10.
1. Design an encoding (a function e from {0, 1, B}∗ to binary strings) such that if e(x) were placed on the tape, it’s possible to uniquely identify the string x.
Solution. Define m : {0,1,B} → {0,1}∗ as 0 → 10,1 → 11,B → 00. Note that this encoding is prefix free (no code is the prefix of another) which means we can read encoded strings without ambiguity. Then, simply encode the entire string character by character
e(x1 …xn) = m(x1)…m(xn).
2. Hence, or otherwise, argue why P machines are equivalent in expressiveness power to T machines up to encoding: That is, given a language L, show that if there exists a T-machine MT such that L(MT ) = L, then there exists a P-machine MP such that L(MP ) = {e(x) : x ∈ L}.
Solution. Foreachtransitionoftheformδ(q,x)=(p,y,D)inT2,adddummystatesinbetween to decode the two bits representing m(x), overwrite with m(y), and move 2 cells in the D direction.
Below is a transition of the form δ(q, x) = (p, y, D) in T2, and it’s corresponding equivalent collection of state and transitions in P to emulate it.
Note that ∗ is shorthand for any character, and ∗/∗, D is shorthand for “read any character, write the same character back, move the tape head in the D direction.
rq,x1 x1/x1, R
∗/∗, D rq,x,reset
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com