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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.