Engineering Mathematics and Automata Theory Concepts
MANOHAR KUMAR K.N
A
s
s
i
s
t
a
n
t
P
r
o
f
e
s
s
o
r
D
e
p
a
r
t
m
e
n
t
o
f
M
a
t
h
e
m
a
t
i
c
s
K
.
S
.
S
c
h
o
o
l
o
f
E
n
g
i
n
e
e
r
i
n
g
a
n
d
M
a
n
a
g
e
m
e
n
t
B
e
n
g
a
l
u
r
u
-
5
6
0
1
0
9
18mat31
Module 1
Engineering Mathematics - III
Turing Machine as an Adder
.
Mr. Sandeep H
Associate Professor
Department of CSE
K.S. School of Engineering and
Management
Bengaluru - 560109
Automata theory and Computability
17CS54
Module 1
Approach for Addition
1.
Numbers are given in Unary 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
TAPE movement for string "11011":
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 and move
Left
Addition of 2 and 2 = 4 is written on TAPE
Input String : 11011
Output String :
1111
State Transition Diagram
We have designed state transition diagram for
adder as follows:
Start scanning string from left to right
•
Pass all '1's and keep moving right
•
Convert '0' to '1' and keep moving right
•
When BLANK(in right) is reached move one step
left
convert '1' to BLANK
•
Keep moving left after that to point start of string
•
Number of '1's is reduced because number of '1'
was increased by one while converting '0' to '1'
State Transition Diagram
8
Turing machine for function
9
Execution Example:
Time 0
Final Result
(=2)
(=2)
10
Time 0
11
Time 1
12
Time 2
13
Time 3
14
Time 4
15
Time 5
16
Time 6
17
Time 7
18
Time 8
19
Time 9
20
Time 10
21
Time 11
22
HALT & Accept
Time 12
Delve into topics such as automata theory, Turing machines, and mathematical approaches for addition using unary numbers. Discover state transition diagrams and gain insights into the workings of Turing machines in computer science.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
18mat31 18mat31 Module 1 Module 1 Engineering Mathematics - III MANOHAR KUMAR K.N MANOHAR KUMAR K.N Assistant Professor Department of Mathematics K.S. School of Engineering and Management Bengaluru - 560109
Automata Automata theory theory and 17CS54 17CS54 and Computability Computability Module 1 Module 1 . Turing Machine as an Adder Mr. Sandeep H Associate Professor Department of CSE K.S. School of Engineering and Management Bengaluru - 560109
Approach for Addition 1. Numbers are given in Unary 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
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 and move Left Addition of 2 and 2 = 4 is written on TAPE Input String : 11011 Output String : 1111
State Transition Diagram We have designed state transition diagram for adder as follows: Start scanning string from left to right Pass all '1's and keep moving right Convert '0' to '1' and keep moving right When BLANK(in right) is reached move one step left convert '1' to BLANK Keep moving left after that to point start of string Number of '1's is reduced because number of '1' was increased by one while converting '0' to '1'
Turing machine for function = + ( , ) f x y x y 1 , 1 R 1 1 , 1 , 1 L R , 0 1 , L , 1 L R q q 1 q q 2 0 3 , R q 4 8
Execution Example: Time 0 y x = 11 x (=2) 1 1 0 1 1 = 11 y (=2) q 0 Final Result x+ y 0 1 1 1 1 q 4 9
1 1 0 1 1 Time 0 q 0 1 , 1 R 1 1 , 1 , 1 L R , 0 1 , L , 1 L R q q 1 q q 2 0 3 , R q 4 10
1 1 0 1 1 Time 1 q 0 1 , 1 R 1 1 , 1 , 1 R L , 0 1 , L L , 1 R q q 1 q q 2 0 3 , R q 4 11
1 1 0 1 1 Time 2 q 0 1 , 1 R 1 1 , 1 , 1 L R , 0 1 , L , 1 L R q q 1 q q 2 0 3 , R q 4 12
1 1 1 1 1 Time 3 1 q 1 , 1 R 1 1 , 1 , 1 L R , 0 1 , L , 1 L R q q 1 q q 2 0 3 , R q 4 13
1 1 1 1 1 Time 4 1 q 1 , 1 R 1 1 , 1 , 1 R L , 0 1 , L L , 1 R q q 1 q q 2 0 3 , R q 4 14
1 1 1 1 1 Time 5 1 q 1 , 1 R 1 1 , 1 , 1 L R , 0 1 , L , 1 L R q q 1 q q 2 0 3 , R q 4 15
1 1 1 1 1 Time 6 q 2 1 , 1 R 1 1 , 1 , 1 L R , 0 1 , L L , 1 R q q 1 q q 2 0 3 , R q 4 16
1 1 1 1 Time 7 q 3 1 , 1 R 1 1 , 1 , 1 L R , 0 1 , L , 1 L R q q 1 q q 2 0 3 , R q 4 17
1 1 1 1 Time 8 q 3 1 , 1 R 1 1 , 1 , 1 R L , 0 1 , L L , 1 R q q 1 q q 2 0 3 , R q 4 18
1 1 1 1 Time 9 q 3 1 , 1 R 1 1 , 1 , 1 R L , 0 1 , L L , 1 R q q 1 q q 2 0 3 , R q 4 19
1 1 1 1 Time 10 q 3 1 , 1 R 1 1 , 1 , 1 L R 1 , L , 0 L , 1 R q q 1 q q 2 0 3 , R q 4 20
1 1 1 1 Time 11 q 3 1 , 1 R 1 1 , 1 , 1 L R , 0 1 , L , 1 L R q q 1 q q 2 0 3 , R q 4 21
1 1 1 1 Time 12 q 4 1 , 1 R 1 1 , 1 , 1 L R , 0 1 , L , 1 L R q q 1 q q 2 0 3 , R q HALT & Accept 4 22
