The problem :
Let $\sum$ be the alphabets of 8 symbols :
A word $w \in \Sigma^*$ of length $n$ can be seen as a suite of $n$ columns of 3 bits or $3$ rows of $n$ bits.
These rows can be seen as 3 whole numbers a,b,c in binary.
Show that language $L \subseteq \Sigma^*$ of $w$ such as a + b = c is a regular language.
Example:
because a = 2, b= 3 and c = 5 (2 + 3 = 5)
My problem :
There's a theorem that if we show that $L^r$ is regular then $L$ is regular.
So i have to draw the reverse automaton of this but i am not sure how to do. There must be a pattern to recognize to draw this easily but i don't see it.
It's been proposed that we read the less significative number first. (the first column on the right)
Also it will be easier to draw the automaton if you replace each symbols by 0,1,2,3,4,5,6,7 ( no need to draw all the columns on the automaton).
Anyone could give me an idea on how to draw this. Would be greatly appreciated. Also, here's a drawing tool if u wanna help out. http://madebyevan.com/fsm/ Thank you.
Edit for answer below
Best Answer
We need to remember if there was carry bit, and if word we read so far is correct. So, 3 states will be enough: valid without carry bit ($a$), valid with carry bit ($b$), invalid ($c$). Initial state is $a$, accepting state is also $a$.
If we read $n$ bits so far, giving number $x$ in the first row, $y$ in the second and $z$ in the third, automaton will be in state $a$ iff $x + y = z$, in state $b$ iff $x + y = 2^n + z$, and in $c$ otherwise.
Transitions are pretty straightforward:
and so on.
In general, if we read $uvw$ and assume $p = 0$ if state was $a$ and $p = 1$ if it was $b$, we need to check $w = u \oplus v \oplus p$ (if not - move to $c$), and move to $a$ if $u + v + p < 2$ and to $b$ otherwise.