patternMinor
Is it possible to construct a finite state automata for a decimal adder?
Viewed 0 times
finiteautomatadecimalpossiblestateforconstructadder
Problem
Suppose the strings are of the form x#y#z , where x,y,z are strings formed from the alphabet $\Sigma=(0,1,2,3,4,5,6,7,8,9)$ . The language is accepted if x+y=z is satisfied, for example : 56#65#121 is accepted, but 2#97#104 is not. Is it possible to find a finite automata for such a language ? I cannot fathom how decimal addition could be carried out using a DFA .
Solution
Interestingly, the question in the body has a negative answer, but the question of the title has a positive answer, if you choose the appropriate representation for the data.
Let me explain this for a binary adder (I let you generalize the argument for a decimal adder). First represent the numbers $x$ and $y$ to be added in reverse binary, with a final $0$ and make sure they have the same length by adding further $0$'s at the end if needed.
For instance, $22 = 2 + 4 + 16$ would be represented by $011010$ and $13 = 1+4+8$ by $101100$. Their sum $35 = 1 + 2 + 32$ is represented by $110001$. Now, just read this data column by column
\begin{matrix}
22 \to &0&1&1&0&1&0\\
13 \to &1&0&1&1&0&0\\
35 \to &1&1&0&0&0&1
\end{matrix}
to get
$(0,1,1)(1,0,1)(1,1,0)(0,1,0)(1,0,0)(0,0,1)$. Taking all representations of the triples $x, y, z$ such that $x + y = z$, you get a regular language on the alphabet $\{0,1\}^3$, recognised by the following automaton
The trick behind this representation is that addition can be obtained by a sequential transducer.
Let me explain this for a binary adder (I let you generalize the argument for a decimal adder). First represent the numbers $x$ and $y$ to be added in reverse binary, with a final $0$ and make sure they have the same length by adding further $0$'s at the end if needed.
For instance, $22 = 2 + 4 + 16$ would be represented by $011010$ and $13 = 1+4+8$ by $101100$. Their sum $35 = 1 + 2 + 32$ is represented by $110001$. Now, just read this data column by column
\begin{matrix}
22 \to &0&1&1&0&1&0\\
13 \to &1&0&1&1&0&0\\
35 \to &1&1&0&0&0&1
\end{matrix}
to get
$(0,1,1)(1,0,1)(1,1,0)(0,1,0)(1,0,0)(0,0,1)$. Taking all representations of the triples $x, y, z$ such that $x + y = z$, you get a regular language on the alphabet $\{0,1\}^3$, recognised by the following automaton
The trick behind this representation is that addition can be obtained by a sequential transducer.
Context
StackExchange Computer Science Q#129164, answer score: 5
Revisions (0)
No revisions yet.