Last Updated: 2023-08-26 14:35:55 Saturday
-- TOC --
Finite Automata，FA，有限状态自动机。（automata是automaton的复数形式，An automaton is a small, mechanical figure that can move automatically. ）
FA是一个不算很复杂的概念，从初始状态开始，FA就根据每一个输入切换自己的状态，状态数量有限，直到最终状态，或者遇到不存在状态转换的路径。其所表达的含义，要根据具体场景。FA可以看作是一个有向图。
Deterministic FA，确定的有限状态自动机。即每个合法的输入，都确定对应了下一个状态，没有歧义。
上图就是正则表达式(a|b)c对应的DFA。
读图：每个节点左边的值，表示由这个值，进入此状态，这个值画在线上有点麻烦，因此就将节点切分成两部分，利用了左边。而右边除了箭头表示状态转换，I是初始状态，E是结束状态。结束状态可能有多个，比如画
a|b的图。
Non-deterministic FA，不确定的有限状态自动机。即存在某个合法的输入，对应了多个下一个状态的情况，状态转换存在多个可能的分支。
或者状态的变换不需要输入也可进行，就看怎么画图，画图的方法，也会与代码的表达方式对应。
两条红色的状态转换路径，对应相同的输入c。（判断哪一种转换才是正确的，是正则表达式匹配判断的问题）
本文链接：https://cs.pynote.net/ag/202308255/
-- EOF --
-- MORE --