This question already has an answer here:

Σ(alphabet) contains 3x1 column matrices [[0],[0],[0]], [[0],[0],[1]] , [[0],[1],[0]]... [[1],[1],[1]] such that each element in the language is a THREE SET of the columns where the bottom row is the sum of the two top rows

example [[0],[0],[1]], [[1],[0],[0]] , [[1],[1],[0]] is an element of the Language


[[0],[0],[1]], [[1],[0],[1]] , [[0],[0],[0]] is not an element of the language.


marked as duplicate by David Richerby, Evil, xskxzr, D.W. Sep 23 at 15:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ What do you mean by a "three set"? If you mean that the words in the langauge are always three characters long, then the language is finite and all finite languages are regular. $\endgroup$ – David Richerby Sep 22 at 17:14
  • 1
    $\begingroup$ Exercise 1.32 of Sipser? $\endgroup$ – AYun Sep 23 at 14:13

Your question was already asked before, but got no answer: How to prove for string of triplets that it is a Regular Language?. I merely summarize the comments given there.

You need to implement binary addition. That is easier when you consider first the language in reverse, the lower bits first.

Standard letters are (in a more intuitive notation) [00|0], [01|1], [10|1], [11|0]. In the last case however, we realize that we should take a carry to the next position. This can be solved by adding a special state for that case, and adapting the letters accordingly.


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