Tentamen (uitwerkingen)
Brunel - Computer Science - CS1005 Logic and Computation Labs (Solutions)
- Vak
- Instelling
These are the Labs used for CS1005 Logic and Computation at Brunel University in which I received a First Class in.
[Meer zien]Voorbeeld 4 van de 95 pagina's
Voorbeeld 4 van de 95 pagina's
In winkelwagen
In winkelwagen
Verkoper
Volgen
cslbrunel
Ontvangen beoordelingen
Voorbeeld van de inhoud
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.
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper cslbrunel. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor $3.89. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 77254 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen
Laatst bekeken door jou
Tentamen (uitwerkingen) ·
USAHS Neuroscience fully solved graded A+ 2023/2024
