论文部分内容阅读
给出了有限自动机的一般定义M=（Q,Σ,R,q0,F）,其中R（Q×（Σ∪{ε}））×Q,特别地,如果R：Q×Σ→Q,则M是确定性有限自动机,该定义统一描述了确定性有限自动机、非确定性有限自动机、带空转移的非确定性有限自动机与部分自动机的概念。在该定义下,证明了确定性有限自动机与非确定性有限自动机的等价性以及正则语言类关于连接、闭包运算的封闭性,因此该定义在理论上是完备的。