The key to this problem is to construct a DFA that can recognize that reverse sum language. With that, we can invoke problem 1.31 to show the sum language is also regular.
The proposed DFA has 3 states, the first state is the start state and represents the last digit has no carry, and the second state is the with carry state represents the last digit has a carry. The third state is the error state. The first state is also the final state.
To simplify discussion, any unrecognized alphabet in a state go to the error state, and it stuck forever there by having all alphabets points towards it.
Now in the start state, we have these transitions:
$ \left(\begin{matrix} 0 \\ 0 \\ 0\end{matrix}\right) $ , $ \left(\begin{matrix} 0 \\ 1 \\ 1\end{matrix}\right) $ and $ \left(\begin{matrix} 1 \\ 0 \\ 1\end{matrix}\right) $ goes to start state.
$ \left(\begin{matrix} 1 \\ 1 \\ 0\end{matrix}\right) $ goes to carry state.
In the carry state, we have these transitions:
$ \left(\begin{matrix} 0 \\ 0 \\ 1\end{matrix}\right) $ goes to the start state
$ \left(\begin{matrix} 0 \\ 1 \\ 0\end{matrix}\right) $ and $ \left(\begin{matrix} 1 \\ 0 \\ 0\end{matrix}\right) $ and $ \left(\begin{matrix} 1 \\ 1 \\ 1\end{matrix}\right) $ does to carry state.
The proposed DFA has 3 states, the first state is the start state and represents the last digit has no carry, and the second state is the with carry state represents the last digit has a carry. The third state is the error state. The first state is also the final state.
To simplify discussion, any unrecognized alphabet in a state go to the error state, and it stuck forever there by having all alphabets points towards it.
Now in the start state, we have these transitions:
$ \left(\begin{matrix} 0 \\ 0 \\ 0\end{matrix}\right) $ , $ \left(\begin{matrix} 0 \\ 1 \\ 1\end{matrix}\right) $ and $ \left(\begin{matrix} 1 \\ 0 \\ 1\end{matrix}\right) $ goes to start state.
$ \left(\begin{matrix} 1 \\ 1 \\ 0\end{matrix}\right) $ goes to carry state.
In the carry state, we have these transitions:
$ \left(\begin{matrix} 0 \\ 0 \\ 1\end{matrix}\right) $ goes to the start state
$ \left(\begin{matrix} 0 \\ 1 \\ 0\end{matrix}\right) $ and $ \left(\begin{matrix} 1 \\ 0 \\ 0\end{matrix}\right) $ and $ \left(\begin{matrix} 1 \\ 1 \\ 1\end{matrix}\right) $ does to carry state.
That's it, we completed the description for the DFA that can recognize the reverse sum language.
That shows the reverse sum language is regular. By problem 1.31, the sum language is also regular!
Q.E.D.
Q.E.D.
No comments :
Post a Comment