ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2014, Vol. 51 ›› Issue (9): 2130-2136.

### On Commutativity of Products of Two Types Fuzzy Finite State Machines

Xie Zhengwei1, Zhai Ying2, Huang Feidan3, Yi Zhong4, Deng Peimin2

1. 1(School of Mathematics and Physics, Jiangsu University of Technology, Changzhou, Jiangsu 213001);2(School of Mathematics and Statistics, Guangxi Normal University, Guilin, Guangxi 541004);3(College of Science, Bijie University, Bijie, Guizhou 551700);4(Faculty of Science, Guilin University of Aerospace Technology, Guilin, Guangxi 541004)
• Online:2014-09-01

Abstract: Automata theory is one of the basic and important theories in computer science. The use of algebraic techniques in determining the structure of automata has been significant. Afterword， Malik et al. applied algebraic techniques to study fuzzy automata or fuzzy finite state machines(ffsm). In this article, the further research on the commutativity of two types ffsm is investigated by algebraic tools such as matrices, semgroups, and so on.Some equivalent characterizations of the commutativity of ffsm are given. It is proved that ffsm are commutative if and only if their state transition matrices are commutative for fuzzy matrix multiplication or the semigroup of strings over input alphabet by congruence relations is commutative. The commutativity of direct product, cascade product,wreath product, and sum of ffsm are discussed. Meanwhile,the concept of commutativity of Mealy-type fuzzy finite state machines (Mffsm) is defined.The commutativity of several products, sum, and quotient for Mffsm are studied in detail.Furthermore,the sufficient and necessary conditions of the commutativity of direct product, sum for ffsm (Mffsm) are obtained as well as the sufficient conditions of the commutativity of wreath product, cascade product for Mffsm.It is also proved that quotient Mffsm maintains the commutativity of Mffsm. Moreover,the algorithm for commutativity of ffsm is presented.

CLC Number: