江苏龙网

  1. 首页 > 生活 > >

怎样用三个状态的FSA解决二进制加法问题

不请自来，分享我个人的一点思考，希望能够抛砖引玉。
先上结论，若两个二进制串还是以每次一个二元组的方式输入，则不存在一个三状态的FSA能够解决二进制加法问题。以下用反证法证明。
==以下是证明==
【怎样用三个状态的FSA解决二进制加法问题】 假设两个二进制串还是以相同的方式输入（每次一个二元组），并假设有一个三状态的FSA能够解决二进制加法问题。
输入一共有四种排列组合，这就意味着在任意一个状态下，至少有两个二元组引发的状态转移是完全一样的。
这两个二元组一定是 (0, 1) 和 (1, 0)，否则可以构造一对二进制串，改变其中一对digit，FSA的输出不变（而二者的和其实改变了）。
所以对每一个状态，输入 (0, 1) 或 (1, 0)，引发的状态转移是一样的，这看起来也很符合直观。同时，类似地可以得出，其同 (0, 0) 和 (1, 1) ，三者引发的状态转移都不一样。
假设三个状态为A、B、C，且不妨设A代表输出1的状态，使用前述结论，可以构造出如下图的一个不完全的状态机：
怎样用三个状态的FSA解决二进制加法问题

注意，这里讨论的是A输入 (0, 1) 或 (1, 0) 后保留在原状态的情况，另一种情况后面会讨论。
除了B和C是对称的可以交换，根据上述限制，其他状态转移都是确定的，例如状态B接受 (0, 1) 只能转移到状态A等。
使用这个不完整的状态机足以推出矛盾了。若初始状态为A，则输入11+01得_10（下划线没有指定最高位），而真实值是100；若初始状态为B，则输入110+011得_101，而真实值是1011；若初始状态为C，情况同初始状态为B的情况。
故A输入 (0, 1) 或 (1, 0) 后不能保留在原状态。
现在假设A输入 (0, 1) 或 (1, 0) 转移到状态B，则状态B也输出1，那么A接受 (0, 0) 或 (1, 1) 都只能转移到状态C，这同前述结论相矛盾（ (0, 0) 和 (1, 1) 引发的状态转移不一样）。
故得出结论，若两个二进制串还是以每次一个二元组的方式输入，则不存在一个三状态的FSA能够解决二进制加法问题。
==证明完毕==
使用其他输入的方式，直观上看状态只会更复杂。三状态的FSA，说白了就是要求算法中使用的所有变量（不包含字符串索引、计算中间结果之类的变量）的所有状态组合只有三个，这似乎实在是太严格了。如果采用进位制加法算法，即一个变量存储当前位而一个变量存储进位，那么二进制加法已经是其中状态数最少的算法了。因此答主个人的主张是不存在这样的FSA，期待有人可以给出证明。
表述多有不严谨之处，请各位指正。


    推荐阅读


    上一篇：靠硬数据来寻找，发现并解决顾客的潜在需要（IBM ），与利用自己的感觉和对客户群体的理解来发现用户需求（Steve Jobs）这两种方式分别有哪些优劣

    下一篇： 「种植」优雅的蓝石莲，花友爱种植，要防止叶子变软，影响观赏性