[go: up one dir, main page]
Scribd
Upload
169 views15 pages

Lecture-7 Turing Machine As Adder

This document provides an overview of a lecture on using a Turing machine as an adder. It introduces the prerequisite knowledge needed, outlines the problem objective of designing a Turing machine to add numbers in unary form. It then demonstrates the process of adding two numbers using a Turing machine by converting 0s to 1s and reducing 1s from the right. It includes the state transition diagram and transition table for the adder Turing machine. Finally, it lists the learning outcomes and references.

Uploaded by

Sumit Srivastava
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
169 views15 pages

Lecture-7 Turing Machine As Adder

This document provides an overview of a lecture on using a Turing machine as an adder. It introduces the prerequisite knowledge needed, outlines the problem objective of designing a Turing machine to add numbers in unary form. It then demonstrates the process of adding two numbers using a Turing machine by converting 0s to 1s and reducing 1s from the right. It includes the state transition diagram and transition table for the adder Turing machine. Finally, it lists the learning outcomes and references.

Uploaded by

Sumit Srivastava
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

B.

Tech, CSE, V Semester, III Year

CS-501: Theory of Computation


UNIT: 5
Turing Machine as a Adder
July-December 2022, Lecture-7

GAURAV DUBEY
Assistant Professor
Department of Computer Science and Engineering
1
Outlines

• Prerequisite of topic
• Problem Objective
• Turing Machine as a Adder
• Assignment
• Learning Outcomes
• SELO
• References

CS-501 2
Prerequisite of topic

Students should have knowledge about the basics of modeling concept of TM


and formal representation of TM.

CS-501 3
Problem Objective
The objective of this lecture is to give the knowledge about
Turing machine and its problems.

CS-501 4
Problem-1
Design a Turing Machine that gives output addition of any two numbers.
Solution:
a. Approach for addition

1. Numbers are given in Uniary form


2. Example: 3 = 111, 2 = 11, 5 = 11111 etc.
3. For addition of 3 and 4, numbers will be given in TAPE as "B B 1 1 1 0 1
1 1 1 B B".
4. Convert '0' to '1' and reduce '1' from right
5. Hence output will be "B B 1 1 1 1 1 1 1 B B B"
6. Total number of '1' in output is = 7 which is addition of 3 and 4

<Reference: R2, R5>


CS-501 <SELO: 6, 8, 9, 12> 5
TAPE movement for string "11011":

<Reference: R2, R5>


CS-501 <SELO: 6, 8, 9, 12> 6
Explanation of TAPE movement

1. Input is given as "11011" (2 + 2)


2. Scan string from left to right
3. Pass all '1’s and convert '0' to '1'
4. Reach BLANK in right
5. Convert rightmost '1' to BLANK

Addition of 2 and 2 = 4 is written on TAPE


Input String : 11011
Output String : 1111

<SELO: 6, 8, 9, 12> <Reference: R2, R5>


CS-501 7
State Transition Diagram

We have designed state transition diagram for adder as follows:


1. Start scanning string from left to right
2. Pass all '1's and keep moving right
3. Convert '0' to '1' and keep moving right
4. When BLANK(in right) is reached move one step left convert '1' to
BLANK
5.Keep moving left after that to point start of string
6. Number of '1's is reduced because number of '1' was increased by one
while converting '0' to '1'

<SELO: 6, 8, 9, 12> <Reference: R2, R5>


CS-501 8
Cont’d…

<SELO: 6, 8, 9, 12> <Reference: R2, R5>


CS-501 9
Transition Table

State/Input 0 1 B
q0 1Rq1 1Rq0
q1 1Rq1 BLq2
q2 BLq2
q3 1Lq3 BRqf
qf

<SELO: 6, 8, 9, 12> <Reference: R2, R5>


CS-501 10
Assignment
1. Construct a Turing machine as comparator.

CS-501 11
Learning Outcomes

Students learn the following outcomes:


•Understand the definition of Turing machine

•Understand the problems solved by Turing machine.

CS-501 12
SELO
 6. Ability to observe and developing sense making, logical skills for abstract
concepts.

 8. Ability to understand subject related concepts clearly along with


contemporary issues.

 9. Application of concepts of topic & it’s technological application.

 12. Computational thinking ability.

CS-501 13
References
 1. Hopcroft, Ullman, “Introduction to Automata Theory, Languages and
Computation”, 2nd Edition, Pearson Education.

 2. K. L. P. Mishra and N.Chandrasekaran, “Theory of Computer Science:


Automata, Languages and Computation”, 3rd Edition PHI.

 3. J. C. Martin, “Introduction to Languages and Theory of Computation”, 2 nd


Edition, TMH.

 4. C. Papadimitrou and C. L. Lewis, “Elements of the Theory of Computation”,


PHI.

 5. https://scanftree.com/automata/turing-machine-introduction

CS-501 14
15

You might also like