I am given an assignment to design a tiny arithmetic unit (from 0 to 15 inclusive) start with 0 and using a DFA. The operations are as follow:

  • increment x+1 and if x+1 is larger than 15 then x+1 goes to 0
  • decrement x-1 and if x-1 is less than 0 then x-1 goes to 15
  • multiplication: 2*x and if 2*x is larger than 15 then we take 2*x - 16
  • division: we simply take the floor of (x/2)

My initial though of the solution was as follow:

1) number the states as follow q0,q1,q2,...,q15 where q0 is the initial state. So the state represent the result of the arithmetic operations

2) the transitions between the states represent the arithmetic operations.

However, soon after I remembered my teacher saying that the DFA return a string of transitions.

My question is can we make the DFA return the final state only (so in my case if it returns qN then the result is N) ? if not how should I solve this problem?


1 Answer 1


I think there's a misconception. DFA by themselves don't return anything. A DFA is a mathematical model. You can interpret the current state of the DFA when it hits an accept state as containing a result, but that's an interpretation you are making that's not part of the mathematical notion of a DFA. Alternatively, you can consider a Moore machine or Mealy machine, which are mathematical models that do produce output; you can think of them as like a DFA but with an extension to allow them to produce output.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.