一类双向模糊有穷自动机

郑兆岳

（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）接受的语言也是等价的。

2 双向有穷自动机

定义2.1 一个非确定双向有穷自动机（2NDFA）是一个五元组 M=（Q，Σ，δ，q0，F），其中 Q 是有限状态集， Σ 是有限输入字母表，δ：Q×（Σ∪{├， ┤}）→ 2Q×{L·S·R}是转移函数，├， ┤不属于 Σ，它们分别为最左和最右结束标志符号。输入串的存储形式为├x┤，其中 x∈Σ，∀（q，σ）∈Q×（Σ∪{├，┤}），δ（q，σ）={（p1，d1），（p2，d2），…，（pm，dm）}，表示 M 在状态q读入字符σ，可以选择地将状态变成p1，同时按d1实现读头的移动；或着将状态变成p2，同时按d2实现对读头的移动；…，或者将状态变成pm，同时按 dm实现对读头的移动。 d1， d2， …，dm∈{L，S，R}，其中，L表示向左，S表示不动，R表示向右移动的方向。

一个确定双向有穷自动机（2DFA）是对所有q∈Q，σ∈Σ∪{├， ┤}，有|δ（q，σ）|≤1，详细给出定义。

定义2.2一个2DFA是一个五元组M=（Q，Σ，δ，q0，F ）其中，Q，Σ，├， ┤和定义 2.1 中一样，且├，┤不属于Σ是最左和最右结束标志符号，δ：Q×（Σ∪{├， ┤}）-→ Q×{L，R，S}。 q0∈Q 是初始状态（起始态），t∈F（F 是接受状态集），r∈Q 是拒绝态，且 r≠t。

对所有的状态 q∈Q 规定 δ（q，┤）=（u，R），δ（q，┤）=（v，L），其中 u，v∈Q，目的是保证读头不跑出串的所在区域。对所有的符号b∈Σ∪{┤}，有δ（t，b）=（t，R），δ（r，b）=（r，R），δ（t，┤）=（t，L），δ（r，┤）=（r，L）。保证机器一旦进入了接受状态，它将停留在此状态中而读头指向任一方向。

例 1.设 M=（Q，Σ，δ，q0，F） 为一 2DFA， 其中Q=（q0，q1，q2，p0，p1，t，r），t为接受状态，r 为拒绝状态，Σ=（0，1），其转移表为

我们可以验证该2DFA，M可识别如下的串{x|x∈{0，1}*且在串x中，0的个数是3的倍数，1的个数是偶数}。

为了描述双向有穷自动机识别一个串的过程，我们来定义它的即时描述（ID）。

引入即时描述（ID）的概念，以代替δ这个概念描述输入符串当前状态和读头现时的位置。若输入字符串 x∈Σ*，x=a1a2…an，a0=├，an+1=┤，a0a1…an+1=├x┤，在某时刻，M处在状态q读头注视第i个字符，则称 2DFA 此时的即时描述 ID 为（q，i），机器的初始ID为（q0，0），即机器在初始状态q0正在注视最左的结束标志符├。

例2.用ID来描述例1中该2DFA M接受串的ID描述序列：

不接受串001010的ID描述序列：

我们来定义2DFA接受的语言。

定义2.3设M为一个双向有穷自动机，则它接受的语言

定义2.4两个双向有穷自动机是等价的，如果它们接受的语言相同，即 L（M1）=L（M2）。

定理2.1[7]双向有穷自动机接受的语言是正则语言。

定理2.2[7]任意一个2DFA，存在一个DFA与之等价。

定理2.3[7]2NFA与FA等价。

定理 2.4[7]任给一个 2NFAM=（Q，Σ，δ，q0，F），存在一个与之等价的 2NFA M'=（Q，Σ，δ'，q0，F），使得对每个可接受的输入串，至少存在一条能到达某终结状态q（∈F）且此时它的读头正注视着最左结束标志符├的可计算路径。

3 双向模糊有穷自动机

定义3.1 一个2NFFA是一个五元组A=（Q，Σ，δ，q0，F），其中，Q，Σ，q0与定义 2.1 的一样，δ 是Q×（Σ∪{├，┤}）×Q×{L，R}的一个模糊子集，即，δ:Q×（Σ∪{├， ┤}）×Q×{L，R}→[0，1]，F 是 Q 的一个模糊子集，它是模糊接受状态。

直观地，δ（q，x，q'，d）是表示当前状态为 q，读头正注视x，下一个状态到达状态q'，且读头将按方向d移动的可能度 （d=L表示向左移动一格，d=R表示向右移动一格）。

定义3.2对某个2NFFA，如果模糊转移函数δ是Q×Σ→Q×{L，R}的一个部分函数，且F是Q的模糊子集，则我们称M为2DFFA。

我们用≺M来定义从ID D1到ID D2，其中，├，┤不属于Σ，w∈Σ，它是D×D上的一个模糊的二元关系 D=Σ*QΣ*。

则M′是只有一个分明终结状态的2NFFA，易验证它们接受的语言是相等的，从而二者是等价的。

定理 3.2 fM1和 fM2分别为 M1=（Q1，Σ，δ1，q01，F1）和 M2=（Q2，Σ，δ2，q02，F2） 接受的语言， 则存在一个2NFFA接受它们语言的并 fM1∨fM2。

推论3.1设f为双向模糊自动机接受的语言，则 f的象集 Im（f）={f（w）|w∈Σ*}为有限集。

设X是一个经典集合，f为X的模糊子集，即，f：X→[0，1]。

定义 3.5 R（f）={f（x）:x∈X，f（x）＞0}，∀λ∈[0，1]，

X上的两个子集 fλ，f[λ]定义为 fλ={x:x∈X，f （x）≥λ}，f[λ]={x:x∈X，f（x）=λ}。

由以上规定的定义，我们有以下的定理：

定理 3.3设 f:Σ*→[0，1]为模糊语言，则下面的称述是等价的：

（1）f能被某非确定性的双向模糊有穷自动机识别。

（2）R（f）是有限的，且 fλ是能被某双向有穷自动机 Mλ识别的正则语言，λ∈R（f）。

3）R（f）是有限的，且 f[λ]是能被某双向有穷自动机 M[λ]识别的正则语言，λ∈R（f）。

（4）f能被某确定性的双向模糊有穷自动机识别。

证明 （1）⇒（2）设 f=fM，其中，M=（Q，Σ，δ，q0，F）是一个非确定性的双向模糊有穷自动机。∀w∈Σ*，有 fM（w）=∨{≺*（q0，w，wq）∧F（p）:q∈Q，w∈Σ*}，由≺*（q0，w，wq）的定义以及[0，1]是一个线性序集，知 R（f）⊆{0，1}∪R（δ）∪R（F）是有限的，即 R（f）是有限的。而且，∀λ∈R（f），w∈Σ*，w∈fλ⇔f（w）≥λ⇔∃p∈Q，≺*（q0，w，wq）∧F（p）≥λ⇔∃p∈Q，≺*（q0，w，wq）≥λ 且 F（p）≥λ⇔w∈L（Mλ），其中 Mλ=（Q，Σ，δλ，q0，Fλ），因此，fλ能被 Mλ识别。

（2）⇒（4）∀λ∈R（f），因为 fλ也能被确定性的双向有穷自动机 M=（Q，Σ，δ，q0，F）所识别，则 λ∧fλ肯定能被某一个 2DFFA M'=（Q，Σ，δ，q0，λ∧F）所识别，其中，λ∧fλ是上 Σ*的一模糊子集，即，λ∧fλ:

由于R（f）是有限的，及模糊正则语言类关于模糊并是封闭的。知 f=∨λ∈R（f）（λ∧fλ）为模糊正则语言，它能被某确定性的双向有穷自动机识别。

（3）⇒（4）和（2）⇒（4）类似，由此 f=∨λ∈R（f）（λ∧f[λ]）。

（4）⇒（1）是显然的，理由：确定性的双向模糊有穷自动机是非确定性的双向模糊有穷自动机的特殊情况。

（4）⇒（3）设 f=fM，M=（Q，Σ，δ，q0，F）是一个确定性的双向模糊有穷自动机，其中F:Q→[0，1]，M接受的语言 fM（w）=V{F（p）:q0w≺*wp，p∈Q，w∈Σ*}，由于 R（f）⊆R（F）∪{1}是有限的，∀λ∈R（f），w∈f[λ]⇔f（w）=λ⇔∃p∈Q，q0w≺*wq 且 F（p）=λ⇔w∈L（M[λ]），其中 M[λ]=（Q，Σ，δ，q0，F[λ]），f[λ]也能被某双向有穷自动机识别。

4 结束语

本文先从经典的角度，介绍了双向有穷自动机与单向有穷自动机所接受的语言是正则语言且等价，给出了由δ来定义的即时描述（ID），它和图灵机的即时描述（ID）文献[1]类似。也得到了结论：任给定一个非确定双向有穷自动机，存在一个至少有一条能到达终结状态的可计算路径的2NFA与之等价。最后，我们把讨论转到模糊上去，也同样用δ定义了双向模糊有穷自动机的即时描述（ID）及其接受的语言。定理3.3详细地给出语言象集R（f）是有限的，及2NFFA与2DFFA的等价性。

[1]Wee W G.On generalizations of adaptive algrithm and application of the fuzzy concept to pattern classification，Ph.D.Thesis，Purdue University， 1967：69-85

[2]John E.HopcroftRajeev MotwaniJeffrey D.Ullman，Introduction to Automata Theory Languages，and Computation [M].ISBN 7-111-14452-X.53-89

[3]Andris Ambuinis，John Watrous.Two-way finite automata with quantun and classical states[J].TheoreticalComputerScience，2002，287：299-311

[4]Viliam Geffert，Carlo Mereghetti，and Giovanni Pighizzini.Complementing Two -Way Finite Automata，DLT（2005），LNS3572：260-271

[5]Viliam Geffert，Carlo Mereghetti，andGiovanni Pighizzini.Converting two-way nondeterministic unary automata into simplerautomata[J].Theoretical computer Science，2003，295：189-203

[6]李永明.模糊系统分析[M].北京：科学出版社，2005：175-204

[7]蒋宗礼，姜守旭.形式语言与自动机理论[M].北京：清华大学出版社，2003：122-125

A kind of two-way fuzzy finite automata

ZHENG Zhao-yue

In this paper，The ID and the accepted language by two-way finite automata and two-way fuzzy finite automata are introducted.We show that its accepted language is regular and the equivalent formulations of two-way nondeteministic finite automata and two-way deteministic finite automata，two-way nondeteministic fuzzy finite automata and two-way deteministicfuzzy finite automata.

two-way fuzzy finite automata;ID（instantaneous description）;regular language;equivalent

O153.1

A

1009-9530（2012）03-0008-04

2011-02-20

郑兆岳（1967-），男，安徽大学数学科学学院硕士研究生，安徽工贸职业技术学院讲师，主要研究方向：模糊集及泛函微分方程。