Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids

摘要

We study fuzzy finite automata in which all fuzzy sets are defined by membership functions whose codomain forms a lattice-ordered monoid L. For these L-fuzzy finite automata (L-FFA, for short), we provide necessary and sufficient conditions for the extendability of the state-transition function. It is shown that nondeterministic L-FFA (N L-FFA, for short) are more powerful than deterministic L-FFA (D L-FFA, for short). Then, we give necessary and sufficient conditions for the simulation of an N L-FFA by an equivalent D L-FFA. Next, we turn to the closure properties of languages defined by L-FFAs: we establish closure under the regular operations and provide conditions for closure under intersection and reversal, in particular we show that the family of fuzzy languages accepted by D L-FFAs is not closed under Kleene closure operation, and the family of fuzzy languages accepted by N L-FFAs is not closed under complement operation. Furthermore, we introduce the notions of L-fuzzy regular expressions and give the Kleene theorem for N L-FFAs. The description of D L-FFAs by L-fuzzy regular expressions is also given. Finally, we investigate the level structures of L-FFAs. Our results provide some insight as to what extend properties of L-FFAs and their languages depend on the algebraic properties of L.