有限状态的有序世界.
我时常觉得<数字逻辑>这门课最大的收获不是那些该死的门, 以及一堆74XX,
而是以一种状态和时序的眼光去分解事件, 乃至世界[狭义的]的有限状态和演进关系.
今天看到篇文章, 用正则表达式判断一个二进制数是否能被3整除, 很有启发.
当然可以把这样一个有限状态机, 看做一种时序的逻辑(事实上本来也是一种时序逻辑),
状态随着输入演进, 并且仅由状态决定输出[Moore机].
为了实现逻辑上的并发, 事实上许多电路的实现都是”暴力”的,
唯有在有限状态下的所有可能均进行了逻辑上的连接处理, 才能实现不考虑因为多级电路产生时延情况下, “瞬时的并行处理”.
这篇文章里的通过有限状态机实现的正则表达式也是如此,
毕竟正则表达式不包含一个可以分支选择的结构, back reference也只是一个简单的前向匹配而已.
因此我们通过状态机的有限状态转换图, 列出了可能的所有会最终到达状态0, 并且输出1的匹配序列.
(当然这里的”所有”, 是指可以通过wildcard和repetation完成简化描述的序列)
最后用正则表达式完成匹配.(当然这里说到的序列枚举的”暴力”操作, 已经和组合逻辑的单纯”暴力组合”有了实质性区别了)
二进制序列模型保证了要成为一个符合条件的有效数字(0自然不考虑了),
第一位必然是1, (否则就必然是0了).
也就是状态机的初始状态非随机, 使得我们在构造最后序列的时候有了很多约束条件可用.
所以, 在这个一定生产环境下, 约束必然有界的有限状态世界中,
还可以有哪些更有趣的实例呢?
Comments (2) ·· Tags: 数字逻辑·正则表达式·状态机