Exam (elaborations)
Brunel - Computer Science - CS1005 Logic and Computation Labs (Solutions)
- Course
- Institution
These are the Labs used for CS1005 Logic and Computation at Brunel University in which I received a First Class in.
[Show more]
Seller
Follow
cslbrunel
Reviews received
Content preview
CS1005 Logic & ComputationLab sheet 1: Turing Machines
(Solutions in bold red font)
1. Print off and read (or read on-line) the lecture slides and notes on Turing Machines.
Please make sure that you clarify any questions you have from them with the GTAs.
2. Write down the binary numbers corresponding to decimal 1 to 20 inclusive.
1=1, 2=10, 3=11, 4=100, 5=101, 6=110, 7=111, 8=1000, 9=1001, 10=1010
11=1011, 12=1100, 13=1101, 14=1110, 15=1111, 16=10000, 17=10001, 18=10010,
19=10011, 20=10100
3. Do the following additions in binary notation without translating into decimal.
Show your working [i.e. the ‘carries’]:
0+1 = 1
1+1 = 10
11+1 = 100
101+1 = 110
111+1 = 1000
11+10 = 101
100+101 = 1001
4. Using the Turing machine table below (the same one as we used in the lecture slides),
state the rows of the table that would be used for the following two inputs on the tape
and what the output would be. Remember, we start at the “*” on the right-hand side
of the binary string in the ‘start’ state. Use the example in your slides to help if you
need to.
Row Current State Current Value Direction to New state to
cell to write move enter
content
1 START * * Left ADD
2 ADD 0 1 Right RETURN
3 ADD 1 0 Left CARRY
4 ADD * * Right HALT
5 CARRY 0 1 Right RETURN
6 CARRY 1 0 Left CARRY
7 CARRY * 1 Left OVERFLOW
8 OVERFLOW Ignored * Right RETURN
9 RETURN 0 0 Right RETURN
10 RETURN 1 1 Right RETURN
11 RETURN * * No Move HALT
,In both cases, the rows of the table used would be 1, 2 and 11. The output of the left
side figure would be 011 and 101 for the right side.
5. Do the same thing with a ‘1’ in every cell, i.e., *111*
In the case where every cell is a’1’, an overflow occurs and so the rows of the table
used would be: 1, 3, 6, 6, 7, 8, 10, 9, 9, 9, 11 and output 1000.
6. Do the same thing with configurations (bit patterns) ‘101’ and ‘001’
For 101, the rows used would be: 1, 3, 5, 9, 11
For 001, the rows used would be the same, i.e., : 1, 3, 5, 9, 11
7. What would be the effect on all the examples above if row 2 instead read as below,
i.e., the value to write has changed from a ‘1’ to a ‘0’
Row Current State Current Value Direction to New state to
cell to write move enter
content
2 ADD 0 0 Right RETURN
The numbers on the tape would stay as they are! There would be no change in
the tape at all.
8. If you have time, in your own words, think of one good reason why state analysis is
so important in computing today.
Testing programs often requires analysis of states – and failure to understand a
system in minute detail can be catastrophic with loss of human life. Using
analysis of states can help understand how a system works in detail – but more
importantly help to uncover ‘error’ states that would cause failure.
, CS1005 – Logic and Computation
Worksheet with Solutions: Lab 2: State Transition and Turing Machine
1. Draw a State Transition Table for the following state machine.
Solution:
2. Given the state diagram of a Turing Machine is:
Answer the following:
a) What is the Tape input language Σ
, CS1005 – Logic and Computation
b) What is the result of the computation of the machine?
Solution:
a) Σ={a,b,c}
b) The result of a computation is to replace the a’s in the input string with c’s and the c’s with
b’s.
3. Given the following Turing Machine
0/0, R 0/0, L
Y/Y, R Y/Y, L
0/X, R 1/Y, L
A B C
Y/Y, R X/X,R
D Y/Y, R
Δ/ Δ,L
Δ/ Δ,L
ACCEPT
and the following tape input:
a) Is this input legal?
b) Given this input, in which state will the machine terminate?
Solution:
a) It is not legal because the machine recognizes L=0n 1n .
b) The machine will terminate in the Reject state. Notice that the Reject State is seldom drawn,
and any transition not drawn on the machine is a Reject State.
4. Define A Turing Machine using a state diagram that recognizes the language anbn cn
Solution:
‣ Starting at left-hand of input, if current cell is empty, accept.
‣ Otherwise, if cell contains an a, change this to an X and move right looking for a corresponding b.
‣ If b is found, change it to a Y and move right looking for a corresponding c.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller cslbrunel. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.89. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
77254 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now