电脑与信息技术
電腦與信息技術
전뇌여신식기술
Computer and Information Technology
2015年
4期
1-4
,共4页
有限自动机%确定性有限自动机%非确定性有限自动机%部分自动机%正则语言
有限自動機%確定性有限自動機%非確定性有限自動機%部分自動機%正則語言
유한자동궤%학정성유한자동궤%비학정성유한자동궤%부분자동궤%정칙어언
给出了有限自动机的一般定义M=(Q,∑,R,q0,F),其中R(∈)(Q×(∑U{ε}))×Q,特别地,如果R:Q×∑→Q,则M是确定性有限自动机,该定义统一描述了确定性有限自动机、非确定性有限自动机、带空转移的非确定性有限自动机与部分自动机的概念.在该定义下,证明了确定性有限自动机与非确定性有限自动机的等价性以及正则语言类关于连接、闭包运算的封闭性,因此该定义在理论上是完备的.
給齣瞭有限自動機的一般定義M=(Q,∑,R,q0,F),其中R(∈)(Q×(∑U{ε}))×Q,特彆地,如果R:Q×∑→Q,則M是確定性有限自動機,該定義統一描述瞭確定性有限自動機、非確定性有限自動機、帶空轉移的非確定性有限自動機與部分自動機的概唸.在該定義下,證明瞭確定性有限自動機與非確定性有限自動機的等價性以及正則語言類關于連接、閉包運算的封閉性,因此該定義在理論上是完備的.
급출료유한자동궤적일반정의M=(Q,∑,R,q0,F),기중R(∈)(Q×(∑U{ε}))×Q,특별지,여과R:Q×∑→Q,칙M시학정성유한자동궤,해정의통일묘술료학정성유한자동궤、비학정성유한자동궤、대공전이적비학정성유한자동궤여부분자동궤적개념.재해정의하,증명료학정성유한자동궤여비학정성유한자동궤적등개성이급정칙어언류관우련접、폐포운산적봉폐성,인차해정의재이론상시완비적.
