Are regular languages closed under addition? Specifically what I mean by addition is, we define $\Sigma_i$ to be the alphabet $\{0, 1, 2, ..., i\}$. Given regular languages $A$ and $B$ under some alphabet $\Sigma_i$, look at $A\times B$.

For every ordered pair $(a, b) \in A\times B$, define the "sum" of this ordered pair as $a+b$, where $a$ and $b$ are numbers in base i. Leading 0's are ignored, so $0^*$is in front of every accepted string. This implies $\epsilon$ is defined as 0.

The language $A+B$ is the set of strings representing all such possible sums.

So far, I know:


This is true in unary ($\Sigma_1$).
This is true for any finite regular languages $A$ and $B$, because any finite language is regular and $A+B$ is finite.
The language $C_n$ = $\{$s $|$ s is a multiple of n in base b$\}$ under $\Sigma_b$ is regular for any $b &gt;= 1$. This means any languages of the form $C_n$ can also be added, as $C_i+C_j=C_{i + j}$, which is also regular. However there are languages like $D$=$\{$s $|$ s starts and ends with a 1} which don't fit this criteria, so this doesn't describe all regular languages.
Yes, they are.

First, consider the alphabet $\Sigma_i^3$ whose symbols are triples of digits (stacked one above each other into a pile of three digits). Over this alphabet, we can define a regular language $A'$ where the string formed by the topmost of the three digits belongs to $A$, a regular language $B'$ where the string formed by middle of the three digits belongs to $B$, and a regular language $C$ where the top two strings sum to the bottom one. $A'$ and $B'$ just use modified automata for $A$ and $B$, while $C$ uses the fact that you can do addition by scanning right-to-left while keeping only a single digit of carry as state.

Then $A'\cap B'\cap C$ is (by closure under intersection) a regular language that recognizes stacks of three strings, one in $A$, one in $B$, and the third in the sum. The homomorphism that strips off the top two digits from a stack leaving only the bottom one takes this to the language you want, and the result follows by closure under homomorphism.