True

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+34 votes

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).

A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits).

+40 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$).

+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

nd in similiar way analyse the fsm

+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.

0

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

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.

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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,750 questions

46,765 answers

140,656 comments

58,515 users