|
|
|
| Automata and Grammars Theory Based on Complete Residuated Lattice-Valued Logic |
| Peng Jia-Yin |
| Key Laboratory of Numerical Simulation of Sichuan Province,College of Mathematics and Information Science, Neijiang Normal University, Neijiang 641112 |
|
|
|
|
Abstract A fundamental framework of automata and grammars theory based on complete residuated lattice-valued logic is preliminarily established. Firstly, the concept of l value regular grammars is introduced. It is proved that any l value language recognized by l value automaton is equivalent to that generated by some l value regular grammar, and conversely, the l value language generated by any l value regular grammar is also equivalent to that recognized by some l value automaton. Afterwards, the concatenations of l value automaton and l value language recognized by l value automaton are depicted. In particular, the l value pumping lemma and L value pumping lemma are built, and then a decision characterization of l value language is presented. Finally, the equivalence between the l value automata with ε-transitions and those without ε-transitions is revealed.
|
|
Received: 01 September 2010
|
|
|
|
|
|
[1] Hopcroft J E, Ullman J D. Introduction to Automata Theory, Languages, and Computation. New York, USA: Addision-Wesley, 1979
[2] Shen Enshao. Model Logic and Theoretical Computer Science. Advance in Mathematics, 1996, 25(3): 193-202 (in Chinese)
(沈恩绍. 模型论逻辑与理论计算机科学. 数学进展, 1996, 25(3): 193-202)
[3] Alon N, Dewdney A, Ott T. Efficient Simulation of Finite Automata by Neural Nets. Journal of the ACM, 1991, 38(2): 498-514
[4] Booch G, Rumbaugh J, Jacobson J. The Unified Modeling Language User Guide. New York, USA: Addison-Wesley, 1999
[5] Hopcroft J E, Ullman J D. Decidable and Undecidable Questions about Automata. Journal of the ACM, 1968, 15(2): 317-324
[6] Raymond D, Wood D, Yu S. Automata Implementation // Proc of the 4th International Workshop on Implementing Automata. Potsdam, Germany, 1996: 189
[7] Yu Sheng. Regular Languages // Rozenberg G, Salomaa A, eds. Handbook of Formal Languages. Berlin, Germany: Springer, 1997, 1: 41-110
[8] Wee W G. On Generalizations of Adaptive Algorithm and Application of the Fuzzy Sets Concept to Pattern Classification. Ph.D Dissertation. West Lafayette, USA: Purdue University, 1967
[9] Santos E S. Maximin Automata. Information and Control, 1968, 13(4): 363-377
[10] Thomason M G, Marinos P N. Deterministic Acceptors of Regular Fuzzy Languages. IEEE Trans on Systems, Man, and Cybernetics, 1974, 4(2): 228-230
[11] Zadeh L A. Fuzzy Sets and System // Proc of the Symposium on System Theory. New York, USA, 1965: 29-37
[12] Shu Lan. The Relation between Fuzzy 3 Grammars and Fuzzy Finite Automata. Mathematica Applicata, 1989, 2(1): 111-112 (in Chinese)
(舒 兰. 关于Fuzzy 3型文法与Fuzzy有限态自动机的关系. 应用数学,1989, 2(1):111-112)
[13] Rosser J B, Turquette A R. Many-Valued Logics. Amsterdam, Netherlands: North-Holland, 1952
[14] Ying Mingsheng. A New Approach for Fuzzy Topology (I). Fuzzy Sets and Systems, 1991, 39(3): 303-321
[15] Ying Mingsheng. A New Approach for Fuzzy Topology (II). Fuzzy Sets and Systems, 1992, 47(2): 221-232
[16] Ying Mingsheng. A New Approach for Fuzzy Topology (III). Fuzzy Sets and Systems, 1993, 55(2): 193-207
[17] Ying Mingsheng. Fuzzifying Topology Based on Complete Residuated Lattice-Valued Logic (I). Fuzzy Sets and Systems, 1993, 56(3): 337-373
[18] Qiu Daowen. Automata Theory Based on Complete Residuated Lattice-Valued Logici I. Science in China: Series E, 2003, 33(2): 137-146 (in Chinese)
(邱道文. 基于完备剩余格值逻辑自动机理论I. 中国科学E辑, 2003, 33(2): 137-146)
[19] Qiu Daowen. Automata Theory Based on Complete Residuated Lattice-Valued Logic Ⅱ. Science in China: Series E, 2003, 33(4): 340-349
(邱道文. 基于完备剩余格值逻辑自动机理论II. 中国科学E辑, 2003, 33(4): 340-349)
[20] Qiu Daowen. Pumping Lemma in Automata Theory Based on Complete Residuated Lattice-Valued Logic: A Note. Fuzzy Sets and Systems, 2006, 157(15): 2128-2138
[21] Pavelka J. On Fuzzy Logic I: Many-Valued Rules of Inference. Mathematical Logic Quarterly, 1979, 25(3/4/5/6): 45-52
[22] Pavelka J. On Fuzzy Logic Ⅱ: Enriched Residuated Lattices and Semantics of Propositional Calculi. Mathematical Logic Quarterly, 1979, 25(7/8/9/10/11/12): 119-134
[23] Pavelka J. On Fuzzy logic Ⅲ: Semantical Completeness of Some Many-Valued Propositional Calculi. Mathematical Logic Quarterly, 1979, 25(25/26/27/28/29): 447-464
[24] Wang Gaojun. Non-Classical Mathematical Logic and Approximate Reasoning. Beijing, China: Science Press, 2000 (in Chinese)
(王国俊. 非经典数理逻辑与近似推理. 北京:科学出版社,2000)
[25] Malik D S, Mordeson J N. Fuzzy Discrete Structures. New York, USA: Physica-Verlag, 2000 |
|
|
|
2011, Vol. 24 
