The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+35 votes
2.3k views
State True or False with one line explanation

A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits).
asked in Theory of Computation by Veteran (59.6k points) | 2.3k views
0
True
0
@Anu gupta plz tell me how
0

2 Answers

+43 votes
Best answer
Finite Automata $(FA)$ or Finite State Machine to add two integers can be constructed using two states:
  • $q_0$: Start state to represent carry bit is $0$
  • $q_1$: State to represent carry bit is $1$
The inputs to $FA$ will be pair of bits i.e. $00, 01, 10,$ and $11$
 
 
 
The FA starts in state $1$ (since carry is $0$) and inputs a pair of bits. If the pair is $11$, the FA outputs a $0$ and switches to state $2$ (since the carry is $1$), where the next pair of bits is input and is added to a carry bit of $1$.
 
Example: Consider the addition of $52$ and $21$
$110100$ - (binary representation of $52$)
$010101$ - (binary representation of $21$)
 
Since adding numbers is done from right to left, the first input symbol is $01$, representing a $0$ in the rightmost (binary) digit of $52$ and a $1$ in the rightmost digit of $21$. The machine enters state  $q_0$ (since there is no carry) and outputs a $1$. The next input is $00$ because both numbers have zero as the second  rightmost digit. The machine enters state $q_0$ and outputs $0$. The next input is $11$. The machine enters state $q_1$ (since the carry is $1$) and outputs $0$. Being in state $q_1$ means that there is a carry from this position into the next. And the remaining bits can be worked out to get $1001001$ (i.e. $73$).
answered by Active (2.3k points)
edited by
0
how to deal with carry..?? i mean when carry is encountered we need to deal with 3 bits..
+1
the 1st state q0 represent carry 0  so whenever input is 11 the sum will be  1+1+0= 0 nd carry will be 1 so we will print the sum 0 and keep track of carry by  making a transition from q0 to q1(represents carry is 1).

nd in similiar way analyse the fsm
+13
+1
perfect :)
+2
An FSM(Mealy) can represent binary adder. Hence, true.
0
A finite state machine can add or subtract two numbers but not multiply but why ???
0
Great Answer
+8 votes
No. Perhaps that wont be possible to add any two arbitrary numbers because that will need a memory element which is not there in a FSM.
answered by Boss (19.7k points)
0
But we have designed it for binary numbers. Why exactly it isn't possible? Can you please explain?
0
I think arbitrary length does not mean infinite length ... so as long as the number is finite i think we can add them ... please clarify !!!
+4

I think we can also add two binary numbers of infinite length by the following FSM. Correct me if I'm wrong.

0
addition with carry is it possible?
0
infintie mean never ending.and if yu are thinking to build machine that works only on all possible combinations  then you have never endging stpes.

aribtary means any,and by godles theorm you will get it as countably infinte.
+4

@habibkhan @Arjun sir, I think Yes it is possible to add two integers of arbitrary length using FSM(mealy machine). Read this and this_too

+2
A finite state machine can add or subtract two numbers why  not multiply  ??

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,599 questions
48,601 answers
155,674 comments
63,739 users