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 .

  • 7
    $\begingroup$ Hint: consider the special case where $x=0$. Can you use a finite automaton to recognize that subset of strings? $\endgroup$ – D.W. Aug 10 '20 at 20:52
  • $\begingroup$ What are you referring to when you say "I am aware of binary addition"? Binary and decimal arithmetic are equivalent here; neither is possible with a FSA but both are possible with a PDA if the input is encoded very carefully. Only unary arithmetic is possible with a PDA using the input encoding you suggest. $\endgroup$ – rici Aug 11 '20 at 2:54
  • $\begingroup$ Sorry, I actually had unary addition in mind. now edited. $\endgroup$ – Arkaprava Paul Aug 11 '20 at 8:00

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.

  • $\begingroup$ Very nice. But using reverse binary is unnecessary since regular languages are closed under reversal. (As humans, we're just more comfortable having carries move forwards. But the DFA is perfectly happy with carries moving backwards, or more accurately carry expectations moving forwards.) $\endgroup$ – rici Aug 12 '20 at 18:09

Definitely, this language is neither a regular language that can be accepted by FA nor a context free language that can be processed by PDA. This fact can be proved easily by pumping lemma.

This language is only a context sensitive language and can be accepted by a LBA (linear bounded automaton) or standard turing machine.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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