recategorized by
14,820 views
70 votes
70 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).
recategorized by

3 Answers

Best answer
86 votes
86 votes
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).$

edited by
7 votes
7 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 votes
0 votes

Finite state automata acts as computational models. If the two integers are converted to decimals and then added then Mealey machine can be designed for computation. Hence its True 

Answer:

Related questions

22 votes
22 votes
3 answers
1
Kathleen asked Oct 5, 2014
7,237 views
Let $p$ and $q$ be propositions. Using only the Truth Table, decide whether $p \Longleftrightarrow q$ does not imply $p \to \lnot q$is True or False.
26 votes
26 votes
5 answers
2
Kathleen asked Oct 5, 2014
7,566 views
State True or False with reasonLogical data independence is easier to achieve than physical data independence.
21 votes
21 votes
5 answers
3
Kathleen asked Oct 5, 2014
3,007 views
Every subset of a countable set is countable.State whether the above statement is true or false with reason.
22 votes
22 votes
2 answers
4
Kathleen asked Oct 4, 2014
4,675 views
State True or False with one line explanationExpanding opcode instruction formats are commonly employed in RISC. (Reduced Instruction Set Computers) machines.