Is $L = \{(x,y,z) | x+y=z\}$ a regular language?

Question

Suppose $x,y,z$ are coded as decimal or their binary representations in an appropriate DFA. Is $L$ regular?

My intuition tells me that the answer is no, because there are infinitely many combinations such that $x+y=z$ and a DFA must contain a finite amount of memory. Is this correct?

Answer 1

This is a funny question, and the answer is: it depends.

First, if $x$, $y$ and $z$ are given sequentially, then pumping lemma implies that triplet $\langle 1(0^n),0,1(0^m)\rangle$ would have to be accepted for multiple values of $m$ and $n$, not necessarily equal.

On the other hand, if the numbers are given simultaneously (e.g. on three tapes, or perhaps by triplets of digits), then it is regular. Consider the case when the automaton processes the numbers right-to-left, the only thing the automaton needs to know is the "carry flag" (or a small number), which, in case of addition can be only $0$, $1$, or $2$. With the other direction, it is just the reversed language.

Also, finite state transducers are even able to carry out addition for numbers given in parallel (i.e. generate $z$ from $x+y$), but there is a difference between deterministic and non-deterministic transducers, so the processing order would matter there.

I hope this helps $\ddot\smile$

Answer 2

Your question is rather imprecise, but it makes it even more interesting...

First, why is your question imprecise? Mainly because you not specify the alphabet and the coding of the triples $(x,y,z)$. So let me modify your question as follows:

Is there an encoding of the triples of integers $(x, y, z)$ on a suitable alphabet $A$ such that the set $L$ is a regular language of $A^*$?

The answer is yes if you take an appropriate coding. The first idea is to represent the natural numbers in reverse binary representation. For instance $22 = 2 + 4 + 16 \to 01101$, $13 = 1+4+8 \to 1011$ and $35 = 1 + 2 + 32 \to 110001$. Next you represent the triples $(x,y,z)$ of natural integers as in this example (note the zeros added at the end of the first two integers in order to have the same length for the representations of $x$, $y$ and $z$) \begin{matrix} 22 &\to &011010\\ 13 &\to &101100\\ 35 &\to &110001 \end{matrix} Finally you take the following representation on the alphabet $A = \{0,1\}^3$. $$ (22, 13, 35) \to \begin{pmatrix} 0\\1\\1 \end{pmatrix} \begin{pmatrix} 1\\0\\1 \end{pmatrix} \begin{pmatrix} 1\\1\\0 \end{pmatrix} \begin{pmatrix} 0\\1\\0 \end{pmatrix} \begin{pmatrix} 1\\0\\0 \end{pmatrix} \begin{pmatrix} 0\\0\\1 \end{pmatrix} $$ Now I claim that the language $L$ of the representations on $A^*$ of all triples $(x, y, z)$ such that $x + y = z$ is regular and accepted by the following DFA (in which the letters are written as horizontal triples rather than as vertical ones to fit the picture on the screen)

Can you see why?

Answer 3

No. Say your numbers are written in base $b$, so your alphabet is symbols 0 to $b - 1$, and (,).

The proof is standard pumping lema: suppose $L$ is regular, let $N$ be the pumping lema constant. Take $\sigma =(10^N,10^N,20^N)$. The pumping lema tells you that a piece of the first number can be repeated without touching the other two. But doing so makes the equation fail, the resulting string isn't in the language.