# Need help trying to figure out DFA

Can anyone please help me try to understand what will the state diagram look like for this question:

Let $$L = \{x_0y_0z_0x_1y_1z_1\ldots x_{n-1}y_{n-1}z_{n-1} \mid \exists n,x,y,z \, x+y=z \land x=\sum_{j=0}^{n-1} x_j2^j \land y=\sum_{j=0}^{n-1} y_j2^j \land z=\sum_{j=0}^{n-1} z_j2^j \land \forall i \, x_i,y_i,z_i \in \{0,1\}\}.$$ Show that $$L$$ is regular. It is sufficient to draw a state diagram.

Try to design your state diagram in a systematic way. Arrange your states in 3 columns (with 1 exception), such that before reading the $$j$$th bit you are in column $$j$$. If at this time, the DFA has to remember 2 bits, you could draw the states in lexicographical order of these 2 bits.

Any help is much appreciated. I've spent more than an hour just trying to understand the question and still could not figure it out.

• I think you should clarify the reference. Feb 9, 2017 at 8:50
• What did you try? Where did you get stuck? We're happy to help with conceptual questions but just solving homework-style exercises for you is unlikely to really help you. Feb 9, 2017 at 12:59

The alphabet for this language is $$\Sigma=\{0,1\}$$. We also have that $$x_i,y_i,z_i\in\Sigma$$. So, notice that $$\sum_{j=0}^{n-1}x_j2^j$$ is simply the decimal equivalent if we assume that the symbols of $$x$$ are expressed as a number in binary. Similar can be said for $$y$$ and $$z$$.

Using this, one can see that the language is effectively the those strings such that if you take every third symbol and form $$x,y,z$$, the numerical equivalent adds up.

For this to be true, for every $$x_i,y_i$$ and carry from the past additions, the corresponding $$z_i$$ should be the correct symbol. If it were not so, then irrespective of the future symbols, we cannot have $$x+y=z$$, and the string can never be accepted.

So, at each iteration, the DFA needs to remember the current values of $$x_i,y_i$$ and the current carry. If the corresponding $$z_i$$ is correct and the carry is $$0$$, it can return to the start state and continue, as this is not going to affect future considerations in any way. This is a final state as at any point when the DFA is in this state, the current sets of $$x_i$$s, $$y_i$$s, and $$z_i$$s are such that the string would be accepted.

If the value of $$z_i$$ is correct but the carry is not $$0$$, then the DFA goes to a different state corresponding to carry being $$1$$. This is not a final state as if the carry was $$1$$ at the end, it would imply that $$x+y\ne z$$ as $$x,y,z$$ must have the same number of symbols.

If the value of $$z_i$$ is incorrect, then the symbol at that "bit" can never be corrected in the future, and the DFA can be sent to a sink state where the string is rejected irrespective of the remaining symbols.

Using the above, the DFA I have drawn (using JFLAP) is as follows:

The first column is when $$x_i,y_i,z_i$$ have been received. $$q_0$$ corresponds to a carry of $$0$$ and is that start and final state. $$q_7$$ corresponds to a carry of $$1$$. The second column is the set of states when $$x_i$$ has been received, and the third is when $$y_i$$ has been received. Then, when $$z_i$$ is received, if it matches $$z_i=x_i+y_i+\text{carry}$$, the DFA goes to state $$q_0$$ or $$q_7$$ depending on the carry. Else, it goes to $$q_{14}$$, which is a sink.

• Solid diagram you've got there. Feb 12, 2017 at 4:23