3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you should clarify the reference. $\endgroup$ – nekketsuuu Feb 9 '17 at 8:50
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Feb 9 '17 at 12:59
4
$\begingroup$

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:

DFA

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.

$\endgroup$
  • 1
    $\begingroup$ Solid diagram you've got there. $\endgroup$ – wogsland Feb 12 '17 at 4:23

Your Answer

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

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