10
$\begingroup$

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.
Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – domotorp
    Nov 8, 2014 at 6:01
  • $\begingroup$ 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). $\endgroup$
    – Phylliida
    Nov 8, 2014 at 6:27
  • $\begingroup$ "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. $\endgroup$
    – babou
    Nov 8, 2014 at 11:46
  • $\begingroup$ 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. $\endgroup$
    – Phylliida
    Nov 8, 2014 at 17:18

2 Answers 2

Reset to default
14
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ That's really awesome. I didn't realize you could use those stacks in that way. Thanks! $\endgroup$
    – Phylliida
    Nov 8, 2014 at 17:13
  • $\begingroup$ 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). $\endgroup$
    – Phylliida
    Nov 8, 2014 at 17:31
  • $\begingroup$ 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? $\endgroup$
    – Phylliida
    Nov 8, 2014 at 17:32
  • $\begingroup$ Yes, there are some technicalities involving padding but they don't really change the basic ideas so I omitted them. $\endgroup$
    – David Eppstein
    Nov 8, 2014 at 23:14
  • $\begingroup$ Cool, that makes sense. $\endgroup$
    – Phylliida
    Nov 8, 2014 at 23:40
9
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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