# Automata and Arithmetics in Canonical Number Systems
## 3 Automata and Canonical Number Systems
Assume that the automaton is in state \(A\), and there are no more digits arriving from the input. Then, by the definition of the transition function \(\delta\), the output of the automaton starting from this state is the sequence \(a_{0}a_{1}\ldots a_{k}\). This means that different states represent different tail releases of the output, i.e., if the automaton is state \(B\
eq A\), then the output without input is different to \(a_{0}a_{1}\ldots a_{k}\)._  
**Theorem 6**. : _The addition automaton, constructed in the proof of Theorem 5, is minimal._Proof. : In the definition of \(\mathcal{A}\) in the proof of the previous theorem, \(S\) is the smallest possible set satisfying the given properties. This means that for any \(A\in S\), there exist proper inputs \(\bar{a},\bar{b}\) such that \(\mathcal{A}(\bar{a},\bar{b})\) terminates in state \(A\). Let \(S=\{A_{1},A_{2},\ldots,A_{n}\}\) and \(\bar{a}_{1},\bar{a}_{2},\ldots,\bar{a}_{n}\), \(\bar{b}_{1},\bar{b}_{2},\ldots,\bar{b}_{n}\) are such that \(\mathcal{A}(\bar{a}_{i},\bar{b}_{i})\) terminates in state \(A_{i}\) for all \(i\in\{1,\ldots,n\}\). Assume that there exists an automaton \(\mathcal{A}^{\prime}\), which executes the same addition as \(\mathcal{A}\), but \(|S^{\prime}|<|S|\), i.e., \(\mathcal{A}^{\prime}\) has strictly fewer states. Then, by the pigeonhole principle, there exist \(1\leq i<j\leq n\) such that \(\mathcal{A}^{\prime}(\bar{a}_{i},\bar{b}_{i})\) and \(\mathcal{A}^{\prime}(\bar{a}_{j},\bar{b}_{j})\) terminates in the same states. By Remark 12, automaton \(\mathcal{A}\) continues with different tail releases from the states \(A_{i}\) and \(A_{j}\), but \(\mathcal{A}^{\prime}\) continues in the same way if there are no more input digits. This is a contradiction because we assumed that \(\mathcal{A}\) and \(\mathcal{A}^{\prime}\) execute the same operation. Hence, the assumption of the existence of \(\mathcal{A}^{\prime}\) is wrong. Although we can not be sure there is no linear time algorithm for multiplication, we have the following. Theorem 4.2: _Let \((P,\mathcal{N})\) be a CNS. Then, there are no finite transducer automaton \(S\) with two input tapes, such that \(\bar{c}=S(\bar{a},\bar{b})\) for all \(\bar{a},\bar{b},\bar{c}\in\mathcal{N}^{*}\) if \(\varphi(Q_{c})=\varphi(Q_{a}\cdot Q_{b})\)._  
Proof. : On the contrary, assume that \(\mathcal{A}=(2,S,\mathcal{N},\mathcal{N},s,\delta)\) executes the multiplication, and \(N=|\mathcal{N}|\). Let \(\bar{a},\bar{c}\in\mathcal{N}^{*}\) satisfying \(\varphi(Q_{c})=\varphi\big{(}Q_{a}^{2}\big{)}\). Then by Lemma 1(vi), and by Theorem 4.2,  
\[\deg(Q_{c}) =L(Q_{c})-1\geq\mathbb{I}(Q_{c})-C_{1}-1=2\mathbb{I}(Q_{a})-C_{1}-1\] \[\geq 2(L(Q_{a})-C_{2})-C_{1}=2\deg(Q_{a})-2C_{2}-C_{1}+1\;.\]  
Set \(n=1+\deg(Q_{a})\), and \(Q_{i}=c_{i}x^{i}+\cdots+c_{0}\) for all \(0\leq i\). (If \(\deg(Q_{c})<i\), then \(Q_{i}=Q_{c}\).) Since the automaton executes the multiplication, there exist \(s_{0},s_{1},\cdots\in S\) such that \(s_{0}=s\), and \(\delta(s_{i},a_{i},a_{i})=(s_{i+1},c_{i})\), for all \(0\leq i\). If \(n\leq i\), then \(a_{i}=0\), and \(Q_{c,n}(x)=\dfrac{Q_{c}(x)-Q_{n}(x)}{x^{n}}\) is determined purely by \(s_{n}\). Since \(\deg(Q_{c,n})\geq n-2C_{2}-c_{1}+1\), there are infinitely many different \(Q_{c,n}\), whence there are infinitely many different corresponding states. However, this is a contradiction since we assumed that \(\mathcal{A}\) is a finite automaton.