Consider the alphabet E = ${[abc] : a, b, c \in 0,1,...,9)} $ Example [234], [567], [897] are symbols of the alphabet. For a string $w \in $ let n($ w $) denote the number represented by $ w $: Example for symbol [345], n([345]) = 345.
Describe a DFA for the language of strings of the form $[x_0y_0z_0][x_1y_1z_1]... [x_ny_nz_n]$ such that
$n(x_n... x_1x_0) + n(y_n... y_1y_0) = n(z_n... z_1z_0)$
This language corresponds to reading the numbers from right to left and position by position; this is how we add numbers by hand. For example, $[819][606][213]$ is in the language because 268 + 101 =369.
I've drawn DFA's of languages before, but it normally deals with binary languages (i.e {a,b}, {0,1}, etc). However, I'm not sure where to start with this since it deals with digits in brackets [] that end up representing arithmetic equations. From what I gathered, drawing a state machine would be impractical since it'll be too big. Thus, I'm sure I have to describe the DFA as a 5 tuple.
$M = (Q, E, d, q_0, F)$
where Q : ?
E = ${[abc] : a, b, c \in 0,1,...,9)} $
d: ?
$q_0 $: ?
F: ?
HINT: The first thing to note is that a character $[abc]$ can be a valid input if and only if
The first two of these are valid if there is no carry from the previous input; the last two are valid if there is such a carry. The second and fourth generate a carry, and the first and third do not.
This means that there are actually five types of characters. If $\Sigma$ is the alphabet of all triples $[abc]$ of digits, let
$$\begin{align*} \Sigma_0&=\{[abc]\in\Sigma:a+b=c\}\;,\\ \Sigma_1&=\{[abc]\in\Sigma:a+b=c+10\}\;,\\ \Sigma_2&=\{[abc]\in\Sigma:a+b+1=c\}\;,\\ \Sigma_3&=\{[abc]\in\Sigma:a+b=c+9\}\;,\text{ and}\\ \Sigma_4&=\Sigma\setminus(\Sigma_0\cup\Sigma_1\cup\Sigma_2\cup\Sigma_3)\;. \end{align*}$$
Each state will have five transitions, one for inputs from $\Sigma_0$, one for inputs from $\Sigma_1$, and so on. You’ll want to use the states to keep track of whether or not there is a carry from the previous input. One state will be a ‘garbage state’: you send the machine to that state when an input ensures that the string will be unacceptable no matter how it continues. For instance, if the automaton is in the initial state and gets an input from $\Sigma_2,\Sigma_3$, or $\Sigma_4$, it should go to the garbage state. If it gets an input from $\Sigma_1$, it should go to a state that indicates that a carry has been produced. If it gets an input from $\Sigma_0$, it is in effect starting from scratch with the next input, so it can stay in the initial state.
That should give you a pretty good start; I’ll leave it to you to work out the rest of the details.