The Australian National University Semester 2, 2020 Research School of Computer Science Tutorial 10 and
Foundations of Computation
The tutorial contains a number of exercises designed for the students to practice the course content. During the lab, the tutor will work through some of these exercises while the students will be responsible for completing the remaining exercises in their own time. There is no expectation that all the exercises will be covered in lab time.
Covers: Lecture Material Week 10
At the end of this tutorial, you will be able to design Turing Machines given a language.
Exercise 1 Even Number of 1s
Design a Turing machine that accepts all strings over {0, 1} that contain an even number of 1s. Assume that the head is
initially on the leftmost bit of the input string.
Represent the Turing machine with a state transition diagram, and give a brief description of the machine. Solution.
The machine has two working states q0 and q1 and termination states q2 and q3.
q0 an even number of 1s has been read
q1 an odd number of 1s has been read
q2 successful termination (a final state)
q3 unsuccessful termination
Initially, when the head is on the leftmost bit of the input string, we have read an even number of 1s (precisely zero 1s which is an even number). We then scan right until we see the first 1, and transition into state q1 (as we have now seen an odd number of 1s, i.e precisely one 1). We then scan right until the next 1 and transition into state q0 as we have now seen an even number of 1s. This continues until we have reached the end of the string (i.e. read a blank Λ). We then terminate
successfully from state q an odd number of 1s).
0,R
(as we’ve seen an even number of 1s) and unsuccessfully from state q 001
(as we then have seen
? Λ Λ,R –
qq
1
Exercise 2
–
0
0,R
13
q
1,R 1,R
? 1
0 Λ
@@ Λ,R
@ @R
Deletion
q
2
Construct a Turing Machine that deletes the symbol at the current head position, by moving all the symbols to the right of this position one tape square to the left, and returns the head to the original position.
Represent the Turing machine using a state transition diagram in the format used in the lectures, and give a brief description of the machine.
Solution.
Overview: • Overwrite current symbol with M
• Move to right-hand end of string (state R)
• Move left, until reaching M; each step remember the symbol seen by going to state L0 or L1; write the symbol previously seen (which is 0 or 1 if you are in state L0 or L1).
State S: Initial: write M
State R: Go to right hand end of string
State K: If still at symbol M then you started at the right hand end of the string, write blank and halt. Otherwise write blank (you are now beyond the new right hand end of the string) and remember symbol seen by going to L0 or L1.
StateLi: Writesymbolremembered(i),remembercurrentsymboljbygoingtoLj,andmoveleft.Repeatthisuntilyou see M; then halt.
State H: Having seen M, and overwritten it, halt.
Exercise 3 Length of the input
Implement a Turing machine that computes the length of its input. That is, construct a Turing machine that replaces its input string with the binary coding of the length of the input string.
Solution. Overview.
• scan to the left and write a ’#’ immediately on the left of the input. State q0 scans to left, and in state q1 we are immediately right of the ’#’ symbol.
• if there is nothing on the right of ’#’, erase the ’#’ and terminate. This is accomplished using states q2 and q3.
• otherwise, scan to the right of the input. In state q5, the head points to the rightmost bit of the input string.
• delete the rightmost bit of the input string, and scan back (to the left) until we have found ’#’. In state q7, the head points to the bit immediately to the left of ’#’.
• increment the binary number to the left of ’#’. This is as in the lectures, and we are in state q8 after incrementing.
• search to the right until ’#’ is found, move to the square immediately right of ’#’ and repeat (starting again in state
q1 ).
A transition diagram looks as follows:
q3 #
Λ,S
q2 Λ
0 Λ,L 1 0,L 1,R
Λ1Λ
#,R 1,R
start q0 q1 0 q4
0,R 10
Λ,L
q5 01
Λ,L Λ,L
1,L
0,R
# 1q60 #,R 1,L 0,L
# #,L
0
1 q 1,R q 1
1,R 8 Λ 7 0,L 1,R
Exercise 4
0 0,R
Selective Removal
Give the state change diagram for a Turing machine that takes a tape containing a string of ‘a’s and ‘b’s and removes the ‘b’s. The initial string on the tape is terminated at each end by a blank symbol (Λ). If the initial string has n a symbols then the final string will be exactly n ‘a’s with no embedded blanks.
(Hint: the original ‘a’s are all identical, they don’t have to be in the same order in the final string). Solution.
• Overview: The TM repeatedly
– moves to the left end of the string (state S0)
– deletes bs on the left end of the string (state S1)
– deletes the left-most a
– scans right to find a b (or blank beyond the right-hand end) and overwrites it by a (state S2)
• State S0: This is the state that is occupied while the TM scans left to find the end.
• State S1: This state indicates the TM is deleting leading bs while looking for the first a on the tape, if any.
• State S2: In this state the TM is carrying a single a to the right. It replaces the first b it finds by this a, or drops it on the first blank symbol if no more bs are on the tape.
Exercise 5
Adding Two to a binary Number
a,L Λ,R a b
? ? ΛΛ
a Λ,R
– Λ,R – Λ,S –
S S Halt
01
b b,L
@@
@
@
a,L
@Λ
a,S –
S Halt
2
6 a,R
a
The lecture notes give a Turing machine that adds one to a binary number. Construct a Turing machine that adds two instead. Assume the input data is represented on the tape with the least significant bit on the right. For example, the binary number for 139 (decimal) would be
10001011
on the tape. Assume the head is initially somewhere over the input data. Represent the Turing machine by its state transition diagram, and give a brief description of the machine.
Solution. Recall from the lecture notes that we used three states S0, S1, H to respectively do the following things:
S0: move the pointer head to the right most bit of the input;
S1: add 1 to the current bit of the input, move the pointer left one cell, repeat if there is a carry-over; H: halt the Turing machine.
To add two instead, we only need to modify the Turing machine in lecture notes such that it adds one to the two’s digit instead:
0 0,R
–
1 1,R
Exercise 6
?Λ 0 0
– 1 – Λ - 012
S Λ,L S 0,L S 1,S H
6 1,L 6 1,S
1 0,L
String Reversal
Construct a Turing machine which, given a string over the alphabet {a, b}, replaces it by the reverse of that string. For example, if the input is aaababb it will be replaced by bbabaaa. Assume that the read/write head is anywhere over the string to be reversed initially.
Represent the Turing machine using a state transition diagram in the format used in the lectures, and give an description of the machine in plain English.
Solution.
start
S #,R S 01
bb
F Λ,R Halt
B Λ Λ,R
aaΛ a,L a,R Λ,R
Λ#
b,L
b,R
#,L
Λ,R
Λ Λ,R
ab A Λ,R R Λ,R
Λ#
Λ Λ,L
### #,R #,L #,R
aWSWa a,R a Λ 2 Λ b a,R
a,L b,L
babb b,R a,L b,L b,R
Description of the machine.
• Inthefirstphase(marking)ofthismachinesoperation(statesS0andS1)aninputofaaababbbecomes#aaababb#.
• In the main (transfer) phase, successive characters of the source, starting at the right end, are deleted and copied to the right end of the reversed string being built. A typical intermediate state of the tape is #aaabΛΛΛ#bba and the final result of the phase is #ΛΛΛΛΛΛΛ#bbabaaa.
• Last is the cleanup phase (state F) where the markers are deleted (giving bbabaaa). Details of the meanings we associate with the various states is given in the following table.
Exercise 7
S0 Scan left to plant left marker
S1 Scan right to plant right marker
R Scan left to find letter to be moved
A Scan right (over blanks) to marker, remembering a Wa Scan right (over {a, b}) to end and write a
B Scan right (over blanks) to marker, remembering b Wb Scan right (over {a, b}) to end and write b
S2 Scan left (to hash mark) over reversed string
F Scan over blanked-out source and remove 2nd marker
Palindromes
Construct a Turing Machine that recognises palindromes over the alphabet {a, b}. In the initial state the tape of the TM will have a string made up of a’s and b’s with no embedded spaces and with the read head somewhere over the string.
Your machine should halt in an accepting state if (and only if) the string is a palindrome. Your answer should consist of two parts:
• A description in plain English that simply describes how your machines works. • A diagram for your Turing Machine, in the notation used in lectures.
Solution. The machine works by iteratively checking that the leftmost and rightmost symbols on the tape are the same. After each successful match those two symbols are erased. The looping terminates successfully when either
• At the start of an iteration the leftmost symbol is also the rightmost one.
The machine will halt if (and only if) the string is a palindrome. In the following solution, when the machine halts the tape will have just a single T (for True) on the tape and the read head above it.
The machine works by iteratively checking that the leftmost and rightmost symbols on the tape are the•saAmfete.rAefrtaesruereacohf smuactcehsisnfgulsmymatbcohlsththoesetatwpeoisybmlabnokl.s are erased. The looping terminates successfully when either
On sau)cAcetstshfeulstearmt oinfatniointe,rtahteiomnathcheilneeftwmroitsetssythmebsoylmisboalsTo tohnetorigthetmtaopset–onthei.s is strictly optional. b) After erasure of matching symbols the tape is blank.
The state transition diagram of the machine is the following.
a,R b,R a ⇤ ⇤ b
⌧ ? ? ⌧ ⌧ ab⇤
A a,R b,R – A ⇤,L – A à2
a,L b,L a @ ⇤,L ⇤ ⇤
ab T,S a
@
⇤ R@
⇤,R
? ? ⌧ ⌧ @ ⌧ ? ⌧
-S⇤,R-Shalt S⌅ à⇤2
T,S
b ab a,S 6 ✓⇤ 6a
⇤,R a,R b,R
⇤,Lb
T,S
? ⌧ ? ? ⌧ ⌧
⇤
b,S
B -B-B àab⇤2
a , R b , R ⇤ , L ⌃ ⇧?
b
Assignment 4 — -Calc., Grammars, PDAs and TMs — Solutions 6