Question

自动机的分类

Answer 1

下面是三类有限自动机
确定有限自动机(DFA)
自动机的每个状态都有对字母表中所有符号的转移。
非确定有限自动机(NFA)
自动机的状态对字母表中的每个符号可以有也可以没有转移，对一个符号甚至可以有多个转移。自动机接受一个字，如果存在至少一个从 q0 到 F 中标记(label)著这个输入字的一个状态的路径。如果一个转移是「未定义」的，自动机因此不知道如何继续读取输入，则拒绝这个字。
有ε转移的非确定有限自动机(FND-ε或ε-NFA)
除了有能力对任何符号跳转到更多状态或没有状态可以跳转之外，它们可以做根本不关于符号的跳转。就是说，如果一个状态有标记著 ε 的转移，则 NFA 可以处在 ε-转移可到达的任何状态中，直接或通过其他有 ε-转移的状态。从一个状态 q 通过这种方法可到达的状态的集合叫做 q 的 ε-闭包。
尽管可以证明所有这些自动机都「可以接受同样的语言」。你总是可以构造接受与给定的 NFA M 同样语言的某个 DFA M。