（基础数学专业论文）格值正则语言及其截集性质研究.pdf

格值正则语言及其截集性质的研究 梁常建 摘要自动机性质的研究是自动机理论的中的一个重要课题文献 6 , 7 ，8 】在广 泛的代数系统一格半群的意义下给出了个新的自动机模型，即格值有限自动机， 在格半群上研究了自动机及其接受的语言的性质，给出了格值自动机比模糊自动机 和经典自动机具有更强的计算能力因此，对格值自动机及其接受语言的性质的研 究就显得更为重要 本文在6 , 7 ，8 ，1 7 ，1 9 1 的基础上研究了格值自动机及其接受的语言的代数性质、 逼近性质，并进一步讨论了格值正则语言截集的代数性质和逼近性质 自动机及其接受语言的代数性质是指自动机及其接受语言关于交、并、补、闭 包反转、同态、逆同态、商等代数运算的封闭性文 6 ，7 ，8 】在格半群的意义下研究 了格值自动机及其接受的语言的代数性质，指出了格值正则语言关于交、并、补、 闭包、反转、连接、同态、逆同态等代数运算的封闭性成立的条件，文【1 7 ，1 9 】给出 了语言或格值语言可以相互e - 逼近的概念，并给出了一些格值正则语言( n l f a ) 可 被确定型格值正则语言( d n l f a ) e 逼近的条件 本文进一步讨论了格值正则语言的代数性质和逼近性质，首先给出了格值正则 语言的商和可容集的概念，并证明了格值正则语言关于商是封闭的，格值语言，是 格值正则的当且仅当，有一个可容集然后我们给出了格值正则语言可被确定型格 值正则语言c 逼近的一些充分和必要的条件在这些的基础之上，我们研究了格值 正则语言截集的性质，给出了格值正则语言截集关于代数运算的封闭性成立的一些 条件例如，格值正则语言截集的并、交、补在般的群的意义下是封闭的，格值 正则语言截集和正则语言的并、交、连接仍属于格值正则语言的截集，格值正则语 言截集关于同态、逆同态、商，反转是封闭的，但关于交和补不一定封闭我们还 探讨了格值语言或格值正则语言的截集和正则语言的逼近性，给出了一些充分或必 要条件，并且指出了格值语言的逼近性和其截集的逼近性之间是有一定的联系的， 得到了一些结论例如，当格值正则语言的截集可诱导一个c 一覆盖时，该截集可被 一个正则语言e - 逼近 关键词：格半群格值正则语言截集代数性质逼近性质封闭性质 s t u d yo nt h ep r o p e r t i e so fl a t t i c e - v a l u e d l a n g u a g e sa n d t h e i rc u t s l i a n gc h a n g j i a n a b s t r a c tt h ep r o p e r t i e so fa u t o m a t aa r ei m p o r t a n ts u b j e c t si na u t o m a t a t h e o r y i nr e f e r e n c e s 6 , 7 ，8 】，l a t t i c e d - v a l u e da u t o m a t ah a v eb e e nc o n s t r u c t e d i nt h e m o r eg e n e r a la l g e b r a i cs t r u t u r e ：l a t t i c e do r e d e dm o n o i d ，a n dt h ep r o p e r t i e so ft h e l a t t i c e d - v a l u e da u t o m a t aa n dt h e i rl a n g u a g e sa r es t u d i e d f r o mt h e s er e f e r e n c e s ，w e k n o wt h a ta u t o m a t aw i t ht r u t h - v a l u e si nal a t t i c e - o r d e r e dm o n o i da r em o r ep o w e r f u l t h a nf u z z ya u t o m a t aa n dc l a s s i c a la u t o m a t a s o ，t h es t u d yo nt h ep r o p e r t i e so f l a t t i c e d - v a l u e da u t o m a t aa n dt h e i rl a n g u a g e sa r ev e r yi m p o r t a n t o nt h eb a s i so fr e f e r e n c e s 6 ，7 ，8 ，1 7 ，1 9 ，w em a i n l yw o r ko v e rt h ea l g e b r i a cp r o p - e r t i e sa n da p p r o x i m a t i o np r o p e r t i e so fl a t t i c e d v a l u e da u t o m a t aa n dt h e i rl a n g u a g e s i nt h i sp a p e r ，a n dw ea s l os t u d yt h et h ea l g e b r a i cp r o p e r t i e sa n da p p r o x i m a t i o n p r o p e r t i e so ft h ec u t so fl a t t i c e d - v a l u e dr e g u l a rl a n g u a g e s t h ea l g e b r a i cp r o p e r t i e so fa u t o m a t aa n dt h e i rl a n g u a g e sa r ec o n s i d e r e da st h e c l o s u r ep r o p e r t i e so fa l g e b r a i co p e r a t i o n so na u t o m a t aa n dt h e i rl a n g u a g e s s u c ha s i n t e r s e c t i o n ，u n i o n ，q u o t i e n t ，r e v e r s a l ，k l e e n ec l o s u r e ，h o m o m o r p h i s ma n ds oo n t h ea r t i c l e s 6 ，7 ，8 】s h o wt h a ta u t o m a t aa n dt h e i rl a n g u a g e sa r ec l o s e du n d e ra l g e - b r a i co p e r a t i o n si nt h el a t t i c e do r e d e dm o n o i dw i t hs o m ec o n d i t i o n si m p o s e d a n d i nf 1 7 ，1 9 ，t h en o t i o no fa p p r o x i m a t i o ni sg a i n e db e t w e e nl a n g u a g e so rl a t t i c e d - v a l u e d l a n g u a g e s ，a n ds o m ec o n d i t i o n sa r eg i v e ni nw h i c hl a t t i c e d - v a l u e da u t o m a t a ( n l f a ) c a r lb e 一a p p r o x o m a t e db yd e t e r m i n i s t i cl a t t i c e d - v a l u e da u t o m a t a ( d n l f a ) i nt h i st h e s i s ，w ec o n t i n u et os t u d yt h ea l g e b r i a cp r o p e r t i e sa n da p p r o x i m a - t i o up r o p e r t i e so fl a t t i c e - v a l u e da u t o m a t aa n dt h e i rl a n g u a g e s f i r s t ，t h en o t i o n s o fq u o t i e n ta n da d m i s s i b l es e ta r ed i f i n e d ，a n dw es h o wt h a tl a t t i c e d - v a l u e dr e g u l a r l a n g u a g e sa r ec l o s e du n d e rq u o t i e n t ，al a t t i c e d - v a l u e dl a g u a g e ，i sl a t t i c e d - v a l u e d r e g u l a ri fa n do n l yi f h a sa na d m i s s i b l es e t t h e n w eo b t a i ns o m es u f f i c i e n to r n e c o e s s a r yc o n d i t i o n si nw h i c hl a t t i c e d - v a l u e dr e g u l a rl a n g u a g e sc a n b ee - a p p r o x i m a t e d b yd e t e r m i n i s t i cl a t t c e d - v a l u e dr e g u l a rl a n g u a g e s f r o mt h ea b o v ed i s c u s s i o n ，w e i n v e s t i g a t et h ep r o p e r t i e so nt h ec u t so fl a t t i c e d - v a l u e dl a g u a g e s ，g i v es o m ec o n d i - t i o n sa b o u tt h ec l o s u r ep r o p e r t i e so fs o m ea l g e b r a i co p e r a t i o n s ，f o re x a m p l e ，t h e u n i o n ，i n t e r s e c t i o n ，c o m p l e m e n to nt h ec u t so ft h el a t t i c e d - v a l u e dr e g u l a rl a n g u a g e s i i a r ec l o s e di ng e n e r a lg r o u p ，t h eu n i o n ，i n t e r s e c t i o n ，c o c a t e n a t i o nb e t w e e nt h ec u t so f l a t t i c e d v a l u e dr e g u l a rl a n g u a g e sa n dr e g u l a rl a n g u a g e si sa l s oc o n t a i n e di nt h ec u t s o fl a t t i c e d - v a l u e dr e g u l a rl a n g u a g e s ，t h ec u t so fl a t t i c e d - v a l u e dr e g u l a rl a n g u a g e s a r ec l o s e du n d e rh o m o m o r p h i s m ，q u o t i e n t ，r e v e r s a l ，b u tt h e s em a yn o tb et r u ef o r i n t e r s e c t i o na n dc o m p l e m e t t h e nw ed e b a t et h ea p p r o x i m a t i o np r o p e r t i e sb e t w e e n t h et h ec u t so fl a t t i c e d - v a l u e dl a n g u a g e so rl a t t i c e d v a l u e dr e g u l a rl a n g u a g e sa n d r e g u l a rl a n g u a g e s ，g i v es o m ec o n c l u s i o n s ，a n ds h o wt h a te - a p p r o x i m a t i o nb e t w e e n l a t t i c e d - v a l u e dl a n g u a g e sa n de - a p p r o x i m a t i o nb e t w e e nt h ec u t so ft h el a t t i c e dl a n - g u a g e sa r er e l a t e di ns o m ee x t e n t f o re x a m p l e i fa c u to fal a t t i c e d - v a l u e dr e g u l a r l a n g u a g ec a ni n d u c eae - c o v e r ，t h e n i tc a nb ee a p p r o x i m a t e db ya r e g u l a rl a n g u a g e k e y w o r d s ：l a t t i c e - o r d e r e dm o n o i dl a t t i c e - v a l u e dr e g u l a rl a n g u a g e s c u t s a l g e b r a i cp r o p e r t i e sa p p r o x i m a t i o np r o p e r t i e s c l o s u r ep r o p e r t i e s i i i 学位论文独创性声明 本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成果尽我所知，除文中已经注明引用的内容外，论文中不 包含其他个人已经发表或撰写过的研究成果，也不包含为获得陕西师范 大学或其它教育机构的学位或证书而使用过的材料对本文的研究做出 重要贡献的个人和集体，均已在文中作了明确说明并表示谢意 一 j ，h 作者签名：蕴! i i 逢日期：三宣：! ：! f 学位论文使用授权声明 本人同意研究生在校攻读学位期间论文工作的知识产权单位属陕西 师范大学本人保证毕业离校后，发表本论文或使用本论文成果时署名 单位仍为陕西师范大学，学校有权保留学位论文并向国家主管部门或其 它指定机构送交论文的电子版和纸质版；有权将学位论文用于非赢利目 的的少量复制并允许论文进入学校图书馆、院系资料室被查阅；有权将 学位论文的内容编入有关数据库进行检索；有权将学位论文的标题和摘 要汇编出版 作者签名 凄蕊蒸 日期：叠2 ，q 厶! ! i 前言 有限( 经典) 自动机作为计算理论中最简单的数学模型，它不仅是计算机科学 的基础，也为现代计算理论提供了可靠的形式理论，而且在汇编语言，编译语言和 算法设计等方面有着重要的应用 自从z a d e h1 9 6 5 年提出模糊集合理论以后，1 9 6 9 年s a n t o s 和w e ew g 利用 模糊集的方法研究自动机理论。提出了模糊有限自动机的概念，开始了模糊计算理 论的研究，为不确定环境下的计算提供了一种有用的计算模型，即模糊有限自动机 作为模糊语言的计算模型将经典语言和自然语言有效的联系起来模糊自动机和模 糊语言的讨论已有很多，如模糊语言在水平结构意义下与正则语言有相同的能力及 模糊语言和正则语言关于交、并、补、同态、逆同态、连接、反转等代数运算是封 闭的 最近，邱道文提出了基于完备剩余格逻辑的自动机理论，从而提出了多值逻辑 意义下研究自动机理论的方法正如其所说，以往模糊自动机理论只是对经典问题 的较弱的模糊化，因而缺乏层次结构注意到不确定性环境下的计算需要更为强大 的计算模型及模糊有限自动机自身的局限性，李永明等将自动机理论推广到更为一 般的结构上，即在格半群的意义下研究自动机理论，提出了格值自动机的理论从 而在更广的框架下，把模糊计算建立在更广泛的格值自动机之上 研究结果表明，格值自动机比模糊自动机有更一般的结果，而且能识别更广泛 的形式语言与模糊语言，例如，研究了格值正则语言的交、并、补等代数性质的封 闭性，并给出了几种格值自动机间及格值自动机与模糊有限自动机的关系，得到了 格值正则语言比模糊语言更接近于自然语言，即格值正则语言在水平结构意义下可 以真包含正则语言，表明了格值自动机比模糊自动机有更强的计算能力 研究表明，格值正则语言的水平截集语言应该具有更为丰富的结构，但目前研 究成果很少基于此，本文继续研究了格值正则语言的的一些其他性质，并进一步 在水平结构意义下研究格值正则语言的一些性质，即研究了格值正则语言的截集语 言的代数性质和逼近性质 本文结构安排如下，第一章主要介绍模糊集合理论的基本概念、性质，模糊自 动机和经典自动机的基本概念和性质，以及格半群的基本概念，性质第二章首先 给出了格值自动机及其语言的基本概念和代数性质，接着进一步研究了格值自动机 的逼近性，给出了格值正则语言可被确定型格值正则语言逼近的一些条件第三章 在第二章的基础上进一步研究了作为格值正则语言表现形式的截集语言的代数性质 以及格值正则语言的截集和正则语言之间的逼近性，并将语言的逼近性和其截集的 1 逼近性作了一定程度的联系但由于格半群的复杂性，我们一些性质的研究限制在 了实数单位区间 o ，1 】，例如，我们虽然证明了格值正则语言的截集在一般群的意义 下关于并是封闭的，但对于一般的格半群我们还不清楚格值正则语言的截集语言关 于并是否是封闭的，因此，这些也就降低了对格值正则语言及其截集性质研究的完 美性 2 第一章预备知识 本章简要介绍本文所需要的相关基础知识，包括模糊集合理论，模糊与经典自 动机理论以及格半群方面的一些基本概念、性质和定理 1 1模糊集合的基本概念与性质 本节主要参考了文献 15 】 定义1 1 1 设x 是经典集合，称映射a ：x 一 0 ，1 】为x 上的模糊集 v x x ，称a ( x ) 为x 对a 的隶属度，函数a ( x ) 也称为模糊集a 的隶属函数 注：定义1 1 1x 上模糊集的全体记为f ( x ) ，即f ( x ) = ( a i a 为x 上的模 糊集) 特别的，当a 的值域退化为 o ，1 时，a 就是经典集或者说a 为x 上某 子集的特征函数 定义1 1 2 设a ，b f ， a t i t t ) 冬f ( x ) ，其中t 为指标集， ( 1 ) 定义u 坨r a t ：x _ 【0 ，1 】为，v x x ，u 挺t a t ( x ) = v t e t a t ( x ) ，则u t e t a t f ( z ) ，称u t e r a 为 a i t t 的并特别的，au b 为a 与b 的并，其隶属函 数记为aub ( z ) = m a x ( a ( x ) ，b ( z ) ) ( 2 ) 定义n t t a t ：x _ 【0 ，1 】为，比x ，a t t a t ( x ) = a t e t a t ( x ) ，则o t e t a t f ( z ) ，称n 拒t a t 为 a i t t 的交特别的，a nb 为a 与b 的交，其隶属函 数记为anb ( z ) = m i n ( a ( x ) ，b ( z ) ) ( 3 ) 定义a c ：x 一 0 ，1 】为，v x x ，小( z ) = 1 一a ( z ) 则a 。f ( x ) ，称a 。 为a 的补 我们定义了f ( x ) 上的代数运算u ，n ，c 后，显然，( f ) ，u ，n ，c ) 构成一个代 数系统并且该代数系统具有以下性质， ( 1 ) 幂等律；a u a = a ，a n a = a ； ( 2 ) 交换律；a u b = b u a ，a n b = b n a ； ( 3 ) 结合律：u b ) u c = a u ( b o c ) ，( a n b ) n = a n ( b n g ) ； ( 4 ) 分配律：a n ( b u c ) = ( a n b ) u ( a n c ) ，a u ( b n c ) = ( a u b ) n ( a u c ) ； ( 5 ) 吸收律ta n ( a u b ) = a ，a u ( a n b ) = a ； ( 6 ) 两极律一a u x = x ，a o x = a ，a u 0 = a ，a n0 0 ； ( 7 ) 复原律：似。) 。= a ( 8 ) 摩根律：( a u b ) 。= a 。n b 。，( a n b ) 。= a 。u b 。 3 定义1 1 3 设a ，b f ( x ) ， ( 1 ) 若v z x ，有a ( x ) b ( z ) ，则称a 含于b ，记为a b ； ( 2 ) 若v x x ，有a ( x ) = b ( z ) ，则称a 等于b ，记为a = b 定义1 1 4 设a f ( x ) ，a 0 ，1 】，则a 与a 的数积a a 定义为， a a ： o ，1 】，v x x ，a 4 ( z ) = a a a ( z ) 定义1 1 5 对于任意的a 【0 ，1 1 ，模糊集a f ( x ) 的截集a 定义为， a = z l a ( x ) a ，z x 特别的，称a 1 = 扛x l a ( x ) = 1 ) 为a 的核，记为k e r a 称a 0 = 扛 x l a ( x ) o ) 为a 的支撑集，记为s u p p a 定理1 1 1 截集具有以下性质。 ( 1 ) ( a u 口) = a u b x ，( a n b ) x = a n b x ； ( 2 ) 若a b ，贝i la z 玖； ( 3 ) 若a 1 a 2 ，则a a t a a 2 ； ( 4 ) a = n o x a n 定理1 1 2 ( 模糊集的分解定理) 对于任意的a f ( x ) ，有 a = u x e oa l a a 若记蜀为【0 ，1 】中的有理点集( 或稠密集) ，则有 a = u 凰a a 定义1 1 6 称映射t ：【0 ，1 】2 一 0 ，1 】为三角模，如果t 满足如下条件； ( 1 ) v ( 0 ，0 ) = 0 ，t ( 1 ，1 ) = 1 ( 2 ) n c ，b d = t ( n ，b ) 丁( c ，d ) ( 3 妒( n ，b ) = t ( b ，a ) ( 4 ) t ( t ( o ，功，c ) = t ( n ，t ( b ，c ) ) 若三角模还满足t ( n ，1 ) = a ( v a 【0 ，1 】) ，则称t 为t 一模；若三角模t 满足 t ( n ，0 ) = a ( v a 【0 ，1 】) ，则称t 为t 一余模或s 一模 例1 1 1 对于任意的a ，b o ，1 】，定义 ( 1 ) t o ( n ，b ) = a ab = m i n a ，吣，称蜀为取小算子； ( 2 ) 岛( o ，b ) = a vb = m a x a ，6 ) ，称岛为取大算子 容易验证是t 一模，s o 是8 一模若t 是连续的t 一模，并且满足条件t v a ( 0 ，1 ) ，t ( a ，a ) a ，则称t 为阿基米德t 一模 定理1 1 3 三角模具有如下性质： ( 1 ) 对于任意的t 一模t ，都有t t o ； ( 1 ) 对于任意的s 一模s ，都有岛s ； 4 ( 3 ) 设t 为t 一模，则t = t o 兮t ( a ，a ) = a ( v a 【o ，1 】) ； ( 4 ) 设s 为s 一模，则s = 岛营s ( n ，a ) = a ( v a o ，1 】) ， 证明( 1 ) 因为t ( a ，b ) t ( a ，1 ) = a ，且t ( a ，b ) t ( 1 ，b ) = b ，所以t ( a ，b ) a ab ，从而t 蜀 ( 3 )若t = t o ，则t ( a ，a ) = aaa = a ( v a 【0 ，1 】) 反之，若v a 【0 ，1 】， t ( a ，a ) = a ，则a a b = t ( a a b ，a a b ) t ( a ，b ) a a 6 ( 性质1 ) ，所以t ( n ，b ) = a a b ， 即t = t o 类似地，可以证明( 2 ) ，( 4 ) 定义1 1 7 设有两个经典集合x 和) 厂，定义x 和y 的直积为， x y = ( z ，可) i z x ，y y ) 也称直积为笛卡尔积，也称积集 定义1 1 8 直积空间xxy = ( z ，y ) l x x ，y y ) 上的模糊关系是x y 上的一个模糊子集r ，r 的隶属函数r ( z ，y ) 表示了x 中的元素z 和y 中的元素 y 具有这种关系的程度x 到x 上的模糊关系称为x 上的模糊关系 1 2模糊自动机与经典自动机的概念与性质 定义1 2 1 一个( 非确定型) 有限自动机( n f a ) 是一个五元组 a = ( q ，6 ，q o ，f ) ， 其中( 1 ) q 是有限的非空状态集，称q q 为a 的一个状态； ( 2 ) e 是有限的输入字符集； ( 3 ) 6 ：q 一2 口为转移函数，对任意的( q ，“) qx ，5 ( q ，u ) = 口1 ， 表示a 在状态q 读入字符u 时，可以选择的进入状态9 1 ，； ( 4 ) q o q 为a 的初始状态； ( 5 ) f q 为a 终止状态集合，称q f 为a 的终止状态 记e = “1 u 2 1 u 1 ，2 e ) ，”= n - 1 ，o = 仁) ，的正闭包+ = u e 2 u u 驴u ，的克林闭包( 星闭包) p = o u + ，v 0 p 称为的字符串，串 p 中字符出现的总次数叫做该串的长度，记为i e l ，长度为0 的字符串记为空串e 我们将6 的定义域从q 扩充到q p ，得到6 的扩展函数扩：q p 一2 q ， 定义为，对任意的q q ，u e ，口p ： ( 1 ) 占( 口，e ) = q ； ( 2 ) 扩( q ，0 u ) = u p 驴( 口，口) 6 ( p ，缸) 5 一个非确定型有限自动机a 接受的语言l ( a ) 定义为，l ( a ) = o j e p 且 扩( q o ，0 ) f 被非确定型有限自动机接受的语言称为正则语言，记为r 语言 定义1 2 2 一个确定型有限自动机( d f a ) 是n f a 的特殊情况，也是一个五 元组a = ( q ，6 ，9 0 ，f ) ，但转移函数为， 6 ：qx 一q ，v ( q ，u ) q ，6 ( q ，乱) = q ， 其他和非确定型有限自动机有相似的定义 我们说两个自动机a 和b 是等价的如果他们接受的语言是相等的，即l ( a ) = l ( b ) 设a 和b 是e + 上的语言，则记 ( 1 ) a b = 0 1 8 2 0 1 a ，0 2 b ) ，称为a 和b 的连接； ( 2 ) a 月= 1 0 兄i o r = u 。u 2 u 1 ，如果0 = u l u 2 u 。a ，乱1 ，钍2 ，u n 称为a 的反转； ( 3 ) 设h ：一+ ，若满足；v o = u l u 2 u 。，有h ( o ) = h ( u 1 ) h ( u 2 ) 7 l ( ) 则称h 为上的同态映射 定理1 2 1 ( 泵引理) 设r 是正则语言，则存在与r 相关的竹满足： 如果1 0 f n ，则3 x ，y ，z p ，且口= x y z ，使得 ( 1 ) y ； ( 2 ) l x y i 礼； ( 3 ) v k 0 ，有x y z l 定理1 2 2 确定型有限自动机和非确定型有限自动机是等价的 定理1 2 3 正则语言关于并、交、补，反转、接、同态、逆同态是封闭的 以上内容主要参考了文献 3 】，下面内容主要参考了文献【1 5 】 定义1 2 3一个( 非确定型) 模糊有限自动机( n f f a ) 是一个五元组a = ( q ，6 ，( t o ，a 1 ) ，其中q 是有限的非空状态集，是有限的输入字符集，d ：qx e q 一【0 ，1 】为模糊转移函数，即对任意的( q ，u ，p ) q e q ，6 ( q ， i t ，p ) 表示 a 在状态q 读入字符钍时，进入下一个状态p 的可能性程度， a o ，o 1 ：q 一【o ，1 】分别为模糊初态和模糊终态这里【o ，1 】为实数单位区间 模糊转移函数6 的扩充函数扩：q pxq 一 0 ，1 】，定义如下： 州埘。k 瓣， 6 ( q ，日，p ) = v q l q6 ( q ，壮l ，口1 ) 6 ( 一l ，“n ，p ) ，v o = 钍1 札2 u n + ，q l ， 甄一1 q ，u 1 ，u 2 ，u n 6 n f f a 接受的语言，a f ( p ) 定义为：厶( 口) = v 。胙oc r o ( q ) a 扩( 口，0 ，p ) a 盯1 ( p ) ，被n f f a 接受的语言称为模糊正则语言( n f f a 语言) 称任意的，f ( p ) 为模糊语言，其中p ( p ) = f i r ：p 一【0 ，1 m 当我们把一个模糊有限自动机的模糊转移函数的值域限制在 o ，1 ) 时，即6 ： qxe xq 一 o ，1 ) ，则模糊有限自动机就成为通常的非确定型有限自动机特别 地，若对任意的q q ，u u ，存在唯一的p q ，使得5 ( q ，u ，p ) = 1 ，且对任意的 r q ，有5 ( q ，7 1 , ，r ) = 0 ，则得到通常的确定型有限自动机的概念 定义1 2 4 一个确定型模糊有限自动机( d f f a ) 是个五元组a = ( q ，5 ，v r o 盯1 ) ，其转移函数6 为分明的，即6 ：q e q ，v ( q ，u ) qx ，6 ( q ，u ) = d q ，印，口1 ) 如f f a 中 d f f a 接受的语言厶f ( e ) 定义为：厶( 口) = v 。o 印( q ) 毋( 扩( g ，口) ) 定理1 2 4 模糊有限状态自动机和确定型模糊有限状态自动机是等价的 定理1 2 5 设f f ( ) 是可以被模糊有限自动机接受的语言，则，的象集 i m ( f ) = s ( o ) l o ) 【0 ，1 为有限集 定理1 2 6 若，是模糊正则语言，则对任意的a 1 0 ，1 1 ， 是上的正则语 言 定理1 2 7 若，是模糊语言，则，是模糊正则语言的充分必要条件是：，的象 集为有限集，且任意的a 0 ，1 1 ， 是上的正则语言这时，= v x e j 。( ，) ( a a ) 1 3格半群的基本概念与性质 本节主要参考了文献【7 ，1 5 】 定义1 3 1 设尸为非空集合，若p 上的二元关系s 满足( 1 ) 自反性，( 2 ) 反 对称性，( 3 ) 传递性三条件，则称( p ) 为偏序集 如果对于任意的a ，b p 必有o b 或者b a ，则称p 为线性序集( 全序集) 如果存在a p 使得v b p 都有a b ，则称a 为p 的最小元素 若存在a 尸使得v b p 都有b a ，则称a 为尸的最大元素 若p 有最小元素或最大元素，则最小元素或最大元素是唯一的，为此，记0 为 最小元素，1 为最大元素 定义1 3 2 设v 和a 分别表示偏序集( l ，) 上的上确界运算和下确界运算， 若对于任意的a ，b l ，a vb 和ab 都存在，则称l 为一个格 若己的任意子集都存在上确界