<p>Yes. I give a NFA that reads the word from the end, as even such automata can recognize only regular languages. We also suppose that $A$ and $B$ are given by such automata, $M_A$ and $M_B$. The NFA guesses at every step what the respective digit of $a$ and $b$ is, checks that the addition is correct, and computes the new respective states of $M_A$ and $M_B$. At the end of the word it accepts if and only if both $M_A$ and $M_B$ accept.</p>

CC BY-SA 3.0
2014-11-08T07:37:22.860Z
2014-11-08T07:37:22.860Z
domotorp
<p>Yes, they are.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-11-08T17:13:33.523Z
That's really awesome. I didn't realize you could use those stacks in that way. Thanks!
Phylliida
CC BY-SA 3.0
2014-11-08T17:31:42.363Z
Admittedly this is a little iffy because in this case it only contains sums of strings of the same size, however, because we can "simulate" sums of strings of different sizes by adding zeroes to the left, and it's simple to modify a dfa into another dfa that recognizes 0* in front of all accepting strings (once you construct the summing dfa to recognize C with homomorphism).
Phylliida
CC BY-SA 3.0
2014-11-08T17:32:27.167Z
I suppose the biggest key is that A and B have to be "technically modified" in the same way to be 0*A and 0*B, and once we do that it's sufficient to, for each pair of a and b, find the sum of 0*a+0*b s.t. both values have enough leading 0s to match sizes, and then the result can be stripped of 0s as needed since C is modified in the same way. Was that implied, or is there a simpler way to look at that that I'm missing?
Phylliida
CC BY-SA 3.0
2014-11-08T23:14:11.150Z
Yes, there are some technicalities involving padding but they don't really change the basic ideas so I omitted them.
David Eppstein
CC BY-SA 3.0
2014-11-08T23:40:06.983Z
Cool, that makes sense.
Phylliida
CC BY-SA 3.0
2014-11-08T07:34:43.273Z
2014-11-08T07:34:43.273Z
David Eppstein
<p>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$.</p>

<p>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.</p>

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

<p>So far, I know:</p>

<ul>
<li>This is true in unary ($\Sigma_1$).</li>
<li>This is true for any finite regular languages $A$ and $B$, because any finite language is regular and $A+B$ is finite.</li>
<li>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.</li>
</ul>

CC BY-SA 3.0
2014-11-08T06:01:40.330Z
It is not true that if A is regular in base 2, it is also regular in base 3, consider, e.g., the powers of 2.
domotorp
CC BY-SA 3.0
2014-11-08T06:27:29.663Z
I see, you're right. I edited the question accordingly. I was trying to prove that one, and it seemed true, and then I misunderstood what a homomorphism was and assumed it was true. But it's not, sorry about that. If a language is regular in base b^a for some a>1 it is also regular in any other base b^(a-c) for any 1 <= c < a  however. (so for example, if a language is regular in base 8, it's also regular in base 4 and 2, simply by simulating the base-8 dfa).
Phylliida
CC BY-SA 3.0
2014-11-08T11:46:52.780Z
"This implies ϵ is defined as 0". I do not understand what that means. If 0 and ϵ are the same, then all 0's can be removed, and the number interpretation no longer works.
babou
CC BY-SA 3.0
2014-11-08T17:18:38.700Z
The point is simply that if an empty string ϵ is in an ordered pair, it adds 0 to the other string. Also for any string given that has leading 0s they can be removed. What this means is that 000101 is the same as 101, for example. This is what I meant, if a ϵ shows up in a string *by itself*, than it is equivalent in value with respect to a sum as 0, or 00, or 000 *by themselves*. If those strings are within another string all bets are off though, and this substitution is no longer valid.
Phylliida
<automata-theory>
Are regular languages closed under addition?
Phylliida
# Are regular languages closed under addition?

(Asked by: username_0 on 2014-11-08)

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 >= 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.

**Tags:** automata-theory
> **Comments:**
> **username_1**: It is not true that if A is regular in base 2, it is also regular in base 3, consider, e.g., the powers of 2.  
> **username_0**: I see, you're right. I edited the question accordingly. I was trying to prove that one, and it seemed true, and then I misunderstood what a homomorphism was and assumed it was true. But it's not, sorry about that. If a language is regular in base b^a for some a>1 it is also regular in any other base b^(a-c) for any 1 <= c < a  however. (so for example, if a language is regular in base 8, it's also regular in base 4 and 2, simply by simulating the base-8 dfa).  
> **username_2**: "This implies ϵ is defined as 0". I do not understand what that means. If 0 and ϵ are the same, then all 0's can be removed, and the number interpretation no longer works.  
> **username_0**: The point is simply that if an empty string ϵ is in an ordered pair, it adds 0 to the other string. Also for any string given that has leading 0s they can be removed. What this means is that 000101 is the same as 101, for example. This is what I meant, if a ϵ shows up in a string *by itself*, than it is equivalent in value with respect to a sum as 0, or 00, or 000 *by themselves*. If those strings are within another string all bets are off though, and this substitution is no longer valid.  

---

## 2 answers

### Answer by username_3 on 2014-11-08. Score: 14 | Accepted answer

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.

> **Comments:**
> **username_0**: That's really awesome. I didn't realize you could use those stacks in that way. Thanks!  
> **username_0**: Admittedly this is a little iffy because in this case it only contains sums of strings of the same size, however, because we can "simulate" sums of strings of different sizes by adding zeroes to the left, and it's simple to modify a dfa into another dfa that recognizes 0* in front of all accepting strings (once you construct the summing dfa to recognize C with homomorphism).  
> **username_0**: I suppose the biggest key is that A and B have to be "technically modified" in the same way to be 0*A and 0*B, and once we do that it's sufficient to, for each pair of a and b, find the sum of 0*a+0*b s.t. both values have enough leading 0s to match sizes, and then the result can be stripped of 0s as needed since C is modified in the same way. Was that implied, or is there a simpler way to look at that that I'm missing?  
> **username_3**: Yes, there are some technicalities involving padding but they don't really change the basic ideas so I omitted them.  
> **username_0**: Cool, that makes sense.  

---

### Answer by username_1 on 2014-11-08. Score: 9

Yes. I give a NFA that reads the word from the end, as even such automata can recognize only regular languages. We also suppose that $A$ and $B$ are given by such automata, $M\_A$ and $M\_B$. The NFA guesses at every step what the respective digit of $a$ and $b$ is, checks that the addition is correct, and computes the new respective states of $M\_A$ and $M\_B$. At the end of the word it accepts if and only if both $M\_A$ and $M\_B$ accept.


---

