谈谈状态机

文章预览

题记：上周做 BBL 里讲了我们 Tubi TV 内部做 DSL 的一些简单实践，大家反馈不错。有同事建议我给大家先补补 FSM，之后再进阶 CFG，可能会更顺畅些。想想也是。于是我自个花了一两个小时，重温了一些课件。马上要回过了，做 BBL 是三周后的事情了，就没先忙写 slides，写了篇文章。本欲留作他用，考虑再三觉得不合适，干脆在公众号上发出来。这篇文章有些干，看看能有多少阅读（我估计也就 3000+），会掉多少粉。 在谈论一般意义的状态机时，我们先看看有限状态机，Finite State Machine，简称 FSM。 在计算理论（Theory of computation）中，FSM 是一切的基础，也是能力最为有限的机器。在其能力之上是 CFL（Context Free Language），然后是 Turing Machine。 FSM 解决一个输入序列， ………………………………