郑兆岳

（1.安徽大学 数学科学学院，安徽 合肥 230039；2.安徽工贸职业技术学院，安徽 淮南 232007）

一类双向模糊有穷自动机

郑兆岳1，2

（1.安徽大学 数学科学学院，安徽 合肥 230039；2.安徽工贸职业技术学院，安徽 淮南 232007）

给出经典双向有穷自动机的即时描述，接受（识别）的语言及双向有穷自动机和有穷自动机是等价的，证明它接受的语言是正则语言。由此，把它推广到模糊上去，相应地给出了双向模糊有穷自动机的定义，即时描述及其接受的语言，进一步证明非确定性双向模糊有穷自动机与确定双向模糊有穷自动机接受的语言是等价的。

双向模糊有穷自动机；即时描述；正则语言；等价

1 引言

有穷自动机（FA）是许多重要类型的硬件和软件的有用模型，作为计算理论，它是最简单的数学模型，它的应用已涉及到数字电路的设计，性能检测软件，通信协议和安全交换信息的协议的验证，神经网络等许多方面。自从Zadeh L A 1965年提出Fuzzy集合理论后，1969年，Wee W G利用模糊的方法研究了自动机理论[1]。模糊自动机（FFA）为计算理论提供了一种研究和处理包含模糊性自然语言的有利工具。在文献[2]中主要介绍经典的有穷自动机，而双向的有穷自动机（2FA）在文献[2]，[3]，[4]，[5]中相应地给出过其定义，文献[4]介绍了2FA接受的补语言，文献[5]介绍了非确定性双向一元自动机向单向自动机的变换，文献[6]更详细地介绍了模糊自动机定义及代数性质。本文从确定性双向有穷自动机 （2DFA）接受的语言是正则语言，给出接受的模糊语言的定义，由经典双向有穷自动机与单向有穷自动机的等价性，从模糊化的程度上讨论了非确定双向模糊有穷自动机（2NFFA）和确定双向模糊有穷自动机（2DFFA）接受的语言也是等价的。……