Cheap and Secure Web Hosting Provider : See Now

[Answers] What is this DFA doing (carry bits)?

, , No Comments
Problem Detail: 

I'm looking to understand how can one graph the following DFA given its mathematical definition.

Take for example this (from [1], p. 107):

  • Set of States: $Q = \{q_{\langle carry=0\rangle}, q_{\langle carry=1 \rangle}\}$
  • Alphabet: $\Sigma = \{\langle x_{i}, y_{i}\rangle \mid x_{i},y_{i}\in[0..9] \}$
  • Start State: $s = q_{\langle carry=0\rangle}$
  • Transition Function: $\delta(q_{\langle carry=c\rangle}, \langle x_{i}, y_{i}\rangle) = \langle q_{\langle carry=c'\rangle}, z_{i}\rangle$ where $c'$ is the high order digit of $x_{i} + y_{i} + c$ and $z_{i}$ is the low order digit.

How does one read the required no. of states and the edges with their symbols?


  1. J. Edmonds, How to Think About Algorithms, Cambridge University Press, 2008.
Asked By : mavavilj

Answered By : Luke Mathieson

The problem here is not really in the implementation of the DFA, but in understanding what the DFA is doing. With those who have access to the text, careful reading of the algorithm preceding it should give a deal of understanding.

From the perspective of the DFA, it has two states, as listed in the Set of States, the symbols on the transitions are pairs of numbers, i.e. each "symbol" is written as five characters (for our understanding, we could encode them any sensible way we wanted of course).

The tuple as the right hand side of the transition function is unusual (and as far as I can seem undefined in the text). What is actually represented here is a finite state transducer, which are essentially equivalent to a DFA, but get to produce a symbol of output at each transition. So the $z_{i}$ is what gets written to the output tape that normally doesn't exist. It also doesn't have an accept state, as the output is no longer yes or no, but whatever is written on the tape.

Now, to understand the construction in full, we need to understand what it's trying to do - add two decimal numbers. It does this digit by digit (from right to left). At each individual addition (digits $x_{i}$ and $y_{i}$), there might be a carry digit, which needs to be remembered for the next addition.

When two decimal digits are added, there are only two possible carries: $0$ or $1$. If we already have a carry, this is still true (the limit cases are $x_{i} = y_{i} = c = 0$ and $x_{i} = y_{i} = 9$, $c = 1$). To put this another way, the output of adding two decimal digits and a carry bit is a two digit number $c' z_{i}$, where $c'$ is the carry bit for the next addition and $z_{i}$ is the decimal output digit.

To give an example of the result, here's the transducer for the binary case. Each transition gives the two input digits, the output digit and target state of the transition. Remember that each transition implicitly includes the carry bit in the addition:

Transducer for single digit binary addition with carry.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback