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