摘要
给出了有限自动机的一般定义M=(Q,Σ,R,q0,F),其中R哿(Q×(Σ∪{ε}))×Q,特别地,如果R:Q×Σ→Q,则M是确定性有限自动机,该定义统一描述了确定性有限自动机、非确定性有限自动机、带空转移的非确定性有限自动机与部分自动机的概念。在该定义下,证明了确定性有限自动机与非确定性有限自动机的等价性以及正则语言类关于连接、闭包运算的封闭性,因此该定义在理论上是完备的。
A general definition of finite automata, M=（Q,Σ,R,q0,F）, is proposed, where R（Q×（Σ∪{ε}））×Q, in particular, M is a deterministic finite automaton if R：Q×Σ→Q. This definition unifomaly describe deterministic finite automata, nondeterministic finite automata, nondeterministic finite automata with 8-transition and partial automata. Based on the general definition, the equivalence between deterministic finite automata and nondeterministic finite automata, as well as the closure property of class of regular languages under concatenation operation and Kleene closure （＊） operation are proved. So the definition is theoretically complete.
出处
《电脑与信息技术》
2015年第4期1-4,共4页
Computer and Information Technology
基金
湖北省自然科学基金(项目编号:2014CFB535)
湖北省教育厅科学技术研究重点项目(项目编号:D20131005)
