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.
[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 
