《模糊有穷自动机与单体二阶Lukasiewicz逻辑_ 李永明1 (陕西师范大学 ...doc》由会员分享，可在线阅读，更多相关《模糊有穷自动机与单体二阶Lukasiewicz逻辑_ 李永明1 (陕西师范大学 ...doc（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流模糊有穷自动机与单体二阶Lukasiewicz逻辑_ 李永明1 (陕西师范大学 .精品文档.模糊有穷自动机与单体二阶Lukasiewicz逻辑* 国家自然科学基金(10571112), 国家重点基础研究项目专项经费(2002CB312200), 教育部重点研究项目(107106) 资助. 李永明1 联系人: 李永明，陕西师范大学计算机科学学院, 西安, 710062; E-mail: liyongm; 电话: 029-85310166.（陕西师范大学计算机科学学院, 西安, 710062）摘要：本文引入了单体二阶Lukasiewicz逻辑,
2、进而给出了模糊有穷自动机识别语言的逻辑描述, 证明了多值逻辑意义下的Bchi与Elgot基本定理. 通过引入星-自由模糊语言与非周期模糊语言, 我们完全刻画了可以用一阶Lukasiewicz逻辑定义的模糊语言.关键词：模糊逻辑, 有穷自动机, 单体二阶Lukasiewicz逻辑, 模糊语言, 模糊计算.1 引言形式语言在理论计算机科学研究中占有重要的地位, 对形式语言的刻画与分类一直是其中的一个重要的研究方向. 在这个方面, 一个重要的研究成果就是Chomsky对形式语言的分类体系. 业已证明Chomsky体系的每一类语言都可以用不同的方法进行描述. 对于最基本的正则语言类, 它可以用有穷自动
3、机来识别, 也可以用正则表达式表示, 可以用正则文法来生成, 也可以用有穷半群来刻画等1，2. Bchi与Elgot进一步建立了正则语言与单体二阶逻辑可定义的语言之间的一致性, 并利用一阶逻辑可定义的语言对正则语言进行了分类3，4，5. 最近, Droste与Gastin对此进行了进一步推广, 在经典逻辑框架下, 他们研究了形式幂级数意义下的正则语言的逻辑描述6. 经典的形式语言是一种精确定义的语言, 它对于描述机器语言起到了重要的作用. 但在处理自然语言尤其是人类使用的语言时, 形式语言对于人类使用语言的模糊性的描述能力明显不够. 为此, Zadeh等人提出了模糊语言的概念, 随后又对模糊语
4、言进行了刻画与分类7. 其中模糊正则语言可以用模糊有穷自动机, 模糊正则表达式, 模糊文法等刻画8，9，10，11，12，13，14. 但有关模糊正则语言在模糊逻辑意义下的逻辑描述还未有系统的研究结果. 模糊逻辑意义下的有穷自动机及其对应单体二阶逻辑描述以及分类仍是一个待解决的问题. 本论文将在这个方面做一些研究. 我们在常用的剩余类逻辑-Lukasiewicz模糊逻辑下定义模糊有穷自动机(参见15), 以及对应的单体二阶逻辑的语构与语义, 建立了模糊逻辑意义下的Bchi与Elgot基本定理. 进一步, 我们给出可用一阶Lukasiewicz逻辑定义的模糊语言, 对模糊正则语言给出了一种分类方
5、法.2 模糊有穷自动机识别语言的有关逻辑性质Lukasiewicz逻辑是以真值论域为的模糊逻辑 (从语义角度), 其中定义为, , , . 本节主要研究Lukasiewicz逻辑意义下的有穷自动机, 我们称为模糊有穷自动机.定义2.1. 模糊自动机是五元组, 其中为有限状态集, 为有限字母表, 为的模糊子集, 代表初始状态与终状态, 而为模糊转移关系. 如下命题“为初始状态” 记为 “”.“为终状态” 记为 “”.“输入使状态转移到” 记为 “”.这些命题的真值分别为, , . 我们用表示字母表上的有限串全体构成的集合,表示空串. 与模糊自动机对应的上的模糊可识别谓词定义为, 对输入串，令,
6、则即命题 的真值定义为， 称为模糊自动机识别或接受的上的模糊语言, 也称为上的模糊正则语言.以下记上的模糊正则语言全体为, 则关于模糊并, 交, 补, 连接, Kleene闭包等封闭9，13. 而且针对Lukasiewicz逻辑, 我们还有如下结论.命题 2.1.( 9，16 )对模糊语言, 以下论断等价.(1) .(2) 存在, 以及正则语言使得, 其中表示的特征函数. (3) 存在, 及两两不交的正则语言使得.命题2.2. 设, 则, 其中.证明. 由命题2.1，存在，以及正则语言使得；并且存在以及正则语言使得. 这时易证，由于正则语言的交仍是正则语言，且. 因此，由命题2.1可得，. 证
7、毕.命题2.3. 设, 则，其中，证明. 由于，所以，其中，表示的补，定义为. 注意到 ，由命题2.2知，. 另外，所以 . 证毕. 命题2.4. (13) 设 为同态，（1）若, 则 ; (2) 若满足，对 , 且 , 则 ，其中 .3 单体二阶Lukasiewicz逻辑以及它可定义的模糊语言我们首先回顾单体二阶逻辑(MSO)有关概念.设为字母表, 上的MSO-逻辑公式的语构用如下的BNF形式定义:其中,为一阶变量, 而为二阶集合变量. 下列公式为利用上述形式中的公式推导出的用其他连接词表示的公式:以下用表示公式中出现的全体自由变量, 用表示集合的子集全体构成的集合.设，. 的长度为. 则字
8、可用结构表示，其中 .设为一阶与二阶变量的有限集合, ，一个 指派是一个函数, 对一阶变量, , 对二阶变量, . 若为一阶变量, 规定指派为一个指派, , 而在的其余变量上与定义一致. 同理, 若为二阶变量, , 同样的可以定义指派. . 给定, 关系 按通常方式定义 (2) , 其中的定义域包含了. 明显的, 只依赖于 .通常我们用扩展字母表来对进行表示或编码, 即用字 表示，其中, 而定义为是一阶变量且是二阶变量且, 这样的字与-指派一一对应. 以下我们就用表示这样的字, 并称这时的为-有效指派. 上的其他的字我们也用表示, 其中为在上的投影, 而为在上的投影, 这时称不是有效的-指派,
9、 以区别于-有效指派. 则语言 为有效的指派为可识别的语言, 即正则语言2. 记, . 由Bchi定理, 若 , 则下面的语言是正则语言, 记. 反之, 对上的正则语言, 一定存在MSO-句子使得.下面我们把这个结论推广到模糊逻辑情形. 首先我们定义单体二阶Lukasiewicz(简记为LMSO)-逻辑. 对于模糊逻辑, 有两种类型的逻辑蕴涵: 一种可以用逻辑连接词 “”, “”, 或者 “”表示, 另一种用剩余运算定义. Lukasiewicz逻辑采用第二种方式来定义逻辑蕴涵. 因此, 在定义Lukasiewicz逻辑时, 逻辑蕴涵是一种主要的连接词, 它不能通过其他的连接词而定义.定义 3
10、.1. LMSO-逻辑的公式的语构用如下的BNF形式定义:其中, , 为一阶变量, 而为二阶集合变量. 由此可诱导如下公式以下用表示公式中出现的全体自由变量. 而用表示所有的LMSO-公式之集.定义 3.2. 设, 为有限变量集且, 则的-语义定义为上的模糊语言如下, 其中, 当不是有效的指派, 则; 否则, 归纳地定义如下:以下记. 注意到, 若为句子, 从而无自由变量, 则为上的模糊语言.命题 3.1. 设, , 则 .特别地, 为模糊正则语言为模糊正则语言.证明. 证明是简单的, 只需对公式中出现的连接词与量词的个数施行归纳即可. 证毕.用表示所有的可用上的句子定义的模糊语言. 模糊逻辑
11、意义下的Bchi-Elgot定理表述如下，这也构成本节的主要定理.定理3.1. . 证明. 由下面引理3.1，引理3.2以及引理3.3的结论得证. 引理3.1. 若 为原子的, 则.证明. 若，构造模糊有穷自动机, , 对任意的，, , 而. 对于 的情形，经典构造即可,参见1. 证毕.引理3.2. 若, 且 可识别, 则, , , , 都可识别.证明. 这是因为, , , 且模糊正则语言关于并, 补, 蕴涵运算封闭. 若令 为抹去第行的投影, 即, 对, , 对, . 则, 由于模糊正则语言在投射同态下保持, 所以也是可识别的. 若将一阶变量换为二阶变量, 则可以证明也是可识别的. 证毕.
12、命题3.2. 以上构造模糊自动机的过程是可判定的. 证明. 显然. 引理3.3. 若字母表上的模糊语言是可识别的, 则存在使得为句子, 且. 证明. 由于是可识别的, 所以存在正则语言, 以及使得. 由于是正则的, 存在句子使得, 这时若令, 则易证. 实际上, 我们可以给出的具体构造如下.设 为识别模糊语言的模糊自动机. 对 , 取集合变量, 并令, 设, 并令 , 定义公式如下:其中, , ，也计为.这时, 对 令 表示所有满足公式的-指派 (即)的集合, 而表示所有标记为的路径的集合. 则存在从集合到集合的一一对应. 这是因为, 若为上的一条以为标记的路径, 则定义-指派为, . 则易验
13、证. 反之, 若为-指派且, 由的定义, 构成的一个分解, 则对任意的存在唯一的使得, 且当时, 存在唯一的使得,从而得到唯一的一条路径, 且.定义公式如下,其中, , .这时, 若为中的一条路径, 为对应的-指派, 则有 令, 这时,另外, 明显的, . 为了对空串输入进行处理, 我们令, 其中, 则明显的, . 从而若取, 则为句子, 且 . 证毕.4 可用一阶Lukasiewicz逻辑定义的模糊语言这一节我们来研究可用一阶Lukasiewicz逻辑定义的模糊语言. 定义 4.1. 公式称为一阶公式, 若不包含任何的集合变量, 即用表示上所有的一阶公式.定义 4.2. (1) 模糊语言称为
14、星-自由的 (star-free), 若可通过上的有限语言经过有限次的布尔运算(并, 交, 补), 数量积, 连接运算而得到. (2)模糊语言称为非周期的 (aperiodic), 若是可识别的且满足条件: 存在非负整数, 对任意的 , 恒有 .引理 4.1. 设为模糊语言, 则为星自由的当且仅当存在有限个以及星自由正则语言使得.证明. 设为星自由的模糊语言, 我们针对生成的运算符号个数归纳证明该引理的结论成立.当无运算符号, 这时为上的有限语言, 引理结论自然成立.设为星自由的且满足引理条件, 则存在有限个数以及, 有限个星自由的正则语言以及使得,. 这时, 显然满足引理条件. 而, 其中表
15、示语言的补语言. 从而 满足引理条件. 对, 也满足引理条件. 关于连接运算, 我们有, 从而也满足引理条件. 归纳的, 我们证明了若为星自由的模糊语言, 则引理的结论成立. 反之是显然的. 证毕.引理 4.2. 设为模糊语言, 则为非周期的当且仅当存在有限个 以及非周期正则语言使得.证明. 设模糊语言为非周期的, 从而为可识别的. 由命题2.1, 存在实数 以及正则语言使得, 其中.我们证明各为非周期的语言即可. 因为为非周期的, 所以存在整数使得对任意的, 都有 . 对此, 以及,有 , 所以各都是非周期的正则语言.反之, 若满足引理条件, 由命题2.1, 是可识别的. 因为各都是非周期的
16、, 所以存在正整数, 对任意的, 有 , 所以 , 这说明为非周期的模糊语言. 证毕.引理 4.3. 对一阶公式, 若为非周期的, 则也是非周期的.证明. 令, 因为为非周期的, 由引理4.2, 存在上的非周期正则语言以及实数以使得, 可以要求各 是两两非交的. 对, 恒有 = . 令 . 这时, 下面只要证明为非周期的正则语言即可. 我们先来证明为正则语言. 定义投影为, , 则 , . 最后一个等式成立是因为, 为有效的-指派且当且仅当存在, 使得. 这样就证明了. 由于是上的正则语言, 且正则语言在同态下保持(17), 所以是正则语言. 下面进一步证明是非周期的即可. 由于各是非周期的,
17、 则存在正整数, 对任意的, 有 成立. 取, 我们证明 . 设 , , . 则 . 注意到的定义方式, 以及是非周期的, 且, 说明这个位置在对应位置的外边, 从而由是非周期的, 可知, 由于位置在位置的外边, 从而说明成立. 这说明是非周期的正则语言. 由引理4.2, 得是非周期的模糊语言. 证毕.定理 4.1. 设为模糊语言, 则下列条件等价.(1) 可以由一阶公式表示, 即存在使得 .(2) 为星-自由的模糊语言.(3) 为非周期的模糊语言.证明. 由于星自由的正则语言与非周期的正则语言是一致的, 从而由引理4.1与引理4.2可知条件(2)与条件(3)等价.(1) (2): 设, 为一
18、阶公式, 下面针对中出现的连接词与量词个数进行归纳. 时, 为原子公式, 当时, 为经典的星自由正则语言, 从而也是星自由模糊语言, 而当时, , 后者明显的是星自由模糊语言. 假设时命题成立, 下面考察的情况. 分以下几种情况: (i) , 或者, 或者 , 则由星自由模糊语言的定义, 可知星自由模糊语言关于语言的并, 数量积, 连接运算封闭, 所以在这种情况下, 都有为星自由模糊语言. (ii) , 设 , , 其中, ,都是星自由的, 则为星自由的. (iii) , 则由引理4.3知是非周期的从而星自由的模糊语言.(2) (1): 因为为星-自由的模糊语言, 根据引理4.1, 存在有限个
19、以及星自由正则语言使得. 由于各都是星自由的正则语言, 所以存在一阶公式使得. 令, 则明显的, 为一阶公式且. 证毕.5 结论与后续工作本文在Lukasiewicz逻辑中研究了模糊自动机以及其识别的模糊语言, 给出了单体二阶Lukasiewicz逻辑的语构与语义, 证明了模糊逻辑意义下的Bchi与Elgot定理. 通过引入星自由模糊语言和非周期模糊语言, 完全刻画了可用一阶Lukasiewicz逻辑描述的模糊语言, 给出了模糊正则语言的一种分类方法. 本文是在Lukasiewicz模糊逻辑下讨论问题的, 且真值仅限于单位区间0,1, 而我们知道, 存在多种模糊逻辑体系, 而且对应的逻辑代数更
20、为复杂, 参见18,19, 那么在不同的模糊逻辑体系中本文的理论是否成立仍是需要进一步讨论的问题. 另外, 模糊语言在不同的形式下的相互转换的复杂性与模糊复杂性 20 也有待于进一步研究.参考文献1 Khoussainov B, Nerode A. Automata Theory and its Applications, Boston: Birkuser, 2001.2 Thomas W. Languages, automata and logic, in: G. Rozenberg, A.Salomaa (Eds.) Handbook of Formal Languages, vol. 3
21、, Springer Verlag, 1997, pp. 389-485.3 Bchi J.R. Weak second-order arithmetic and finite automata. Zeitschrifit fur Mathematische Logik and Grundlagen der Mathematik, 1960, 6: 66-92.4 Elgot C.C. Decision problems of finite automata design and related arithmetics. Transactions of the American Mathema
22、tical Society, 1961, 98: 21-52.5 田启家, 沈恩绍, 史忠植. 和正则语言. 计算机学报, 1996, 19(11): 848-853. (Tian Qijia, Shen Enshao, Shi Zhongzhi. and regular language. Chinese Journal of Computer, 1996, 19(11): 848-853.)6 Droste M, Gastin P. Weighted automata and weighted logics. Theoretical Computer Science, 2007, 380:
23、 69-86.7 Lee E T, Zadeh L A. Note on fuzzy languages. Information Sciences, 1969, 1: 421-434.8 Mordeson J N, Malik D S. Fuzzy Automata and Languages: Theory and Applications. Boca Raton, London: Chapman & Hall/CRC, 2002.9 Li Y M, Pedrycz W. Fuzzy finite automata and fuzzy regular expressions with me
24、mbership values in lattice-ordered monoids. Fuzzy Sets and Systems, 2005, 156: 68-92.10 Li Y M, Pedrycz W. The equivalence between fuzzy Mealy and fuzzy Moore machines. Soft Computing, 2006,10(10): 953 - 959.11 Li Y M. Approximation and robustness of fuzzy finite automata. International Journal of A
25、pproximate Reasoning, 2008, 47: 247-257.12 Li Y M, Pedrycz W. Minimization of lattice finite automata and its application to the decomposition of lattice languages. Fuzzy Sets and Systems, 2007, 158: 1423-1436.13 Li P, Li Y M. Algebraic properties of LA-languages. Information Sciences, 2006, 176: 32
26、32-3255.14 Ying M S. A formal model of computing with words. IEEE Transactions on Fuzzy Systems, 2002, 10(5): 640-652.15 Qiu D W. Automata theory based on complete residuated lattice-valued logic. Science in China Series F, 2001, 44(6): 419-429.16 李永明. 模糊系统分析. 北京: 科学出版社, 2005. (Li Yongming. Analysis
27、 of Fuzzy Systems. Beijing: Academic Press, 2005.)17 Hopcroft J E, Ullman J D. Introduction to Automata Theory, Languages and Computation. New York: Addison-Wesley, 1979.18 Hajek P. Metamathematics of Fuzzy Logic. Dordrecht: Kluwer Academic Publisher, 1998.19 王国俊. 非经典数理逻辑与近似推理. 北京: 科学出版社, 2000. (Wan
28、g Guojun. Nonstandard Mathematical Logic and Approximate Reasoning. Beijing: Academic Press, 2000.)20 Li Y M. Approximation and universality of fuzzy Turing machines. Science in China Series F, 2008, DOI: 10.1007/s11432-008-0089-y.Fuzzy Finite Automata and Monadic Second-Order Lukasiewicz LogicYongm
29、ing Li(College of Computer Science, Shaanxi Normal University, Xian, 710062, China)Abstract: We introduce monadic second-order (MSO-) Lukasiewicz logic and prove that the behaviors of fuzzy finite automata are precisely the fuzzy languages definable with sentences of our MSO Lukasiewicz logic. This
30、generalizes Bchi s and Elgots fundamental theorems to fuzzy logic setting. We also consider first-order Lukasiewicz logic and show that star-free fuzzy languages and aperiodic fuzzy languages introduced here coincide with the first-order definable ones.Keywords: Fuzzy logic, finite automata; monadic
31、 second-order Lukasiewicz logic; fuzzy language; fuzzy computation.背景介绍Early in the history of theoretical computer science, it came to light that formal languages would be one of the foundations of further research. Therefore characterizing all languages, or even better sorting them in some hierarc
32、hy, was an important issue. For example, the regular languages can be characterized by finite automata and by regular expressions. Myhill and Nerode independently showed that this is equivalent to a characterization by finite monoids 1,2. The equivalence to monadic second-order logic is due to Bchi
33、and Elgot, and further give a sort of regular languages definable by first-order logic 3,4. Recently, Droste and Gastin gave a further generalization to monadic second-order logic characterization of regular languages in the frame of formal power series6. Classical formal languages are precise defin
34、ed languages, they are very useful in the describing of machine languages. But it is not powerful in the processing of human languages. For this, Zadeh introduced the notion of fuzzy languages and gave some characterizations in 7. For example, fuzzy regular languages can be characterized by fuzzy fi
35、nite automata, fuzzy regular expressions, fuzzy grammars 8, 9, 10, 11, 12, 13, etc. While there is no any results on the monadic second-order logic characterization of fuzzy regular languages. How to characterize fuzzy regular languages by monadic second-order logic in fuzzy setting is an open probl
36、em. We shall do some work in this way. In the frame of well-known residual-logic-Lukasiewicz fuzzy logic, we give the definition of fuzzy finite automata (see 15), and present the corresponding syntactic and semantics of monadic second-order logic, the fuzzy Bchi-Elgot theorem is set up. Furthermore
37、, we give the characterization of fuzzy languages definable by first-order Lukasiewicz-logic, and a sort of fuzzy regular languages is given. We have studied fuzzy automata for many years. In particular, we introduced the notion of lattice-valued automata 9, which forms one of the main topics in the
38、 study of fuzzy automata. Many interesting results have been obtained in this field. The study of monadic second-order fuzzy logic of fuzzy automata is one of these results.作者简介：李永明，男，1966年3月生，博士，教授，博士生导师。1996年在四川大学取得理学博士学位，目前为陕西师范大学计算机科学学院教授，中国计算机学会高级会员，主要研究方向为：计算理论，模糊控制理论，模糊自动机理论，空间推理，量子逻辑以及格上拓扑学.
39、LI Yong-Ming was born in 1966, male. He received the Ph.D. degree in mathematics from Sichuan University, Sichuan, China, in 1996. He is currently a professor at College of Computer Science, Shaanxi Normal University and a CCF senior member. His research interests include computation theory, fuzzy control theory, fuzzy automata theory, spatial reasoning, fuzzy and quantum logic, and topology over lattices.电话：029-85310166（办公室），13891825126（手机）.E-mail: liyongm