# How to prove for string of triplets that it is a Regular Language?

Let Σ2 = {0, 1}, and define Σ = Σ23. Informally, Σ* is the set of triples of the form (a, b, c) where a, b, c are single binary digits. Consider a string s ∈ Σ* : it is a sequence of such triples. Have to “verify” binary addition of numbers in the first two coordinates by checking that it is equal to the third. Let A be the language of such triples such that the concatenation of the first coordinates, as a number, and the concatenation of the second coordinates, as a number, sum to be equal to the third.

For example, if w = (0, 1, 1)(1, 1, 1)(0, 0, 1)(1, 0, 1), this is encoding 01012 + 11002 = 11112, which is false; therefore, w ∉ A. How to prove A is Regular ?

Only thing I could think of is somehow has to prove for Reversal is Regular and then this could be proved, but no further idea.

• Simulate addition with carry. Two states should suffice. – Yuval Filmus Jul 7 '17 at 19:33
• Not getting your point ! Simulate addition with carry. NFA for addition - two states would be enough fine. But missing somethings I guess. – Desperado Jul 7 '17 at 19:52
• Actually I was thinking of a DFA. – Yuval Filmus Jul 7 '17 at 19:53
• yeah DFA is fine. But not able to understand . – Desperado Jul 7 '17 at 19:56
• It's easier to read the bits LSB to MSB. – Yuval Filmus Jul 7 '17 at 19:57