Construction of fuzzy automata from fuzzy regular expressions

Li and Pedrycz have proved fundamental results that provide different equivalent ways to represent fuzzy languages with membership values in a lattice-ordered monoid, and generalize the well-known results of the classical theory of formal languages. In particular, they have shown that a fuzzy language over an integral lattice-ordered monoid can be represented by a fuzzy regular expression if and only if it can be recognized by a fuzzy finite automaton. However, they did not give any efficient method for constructing an equivalent fuzzy finite automaton from a given fuzzy regular expression. In this paper we provide such an efficient method. Transforming scalars appearing in a fuzzy regular expression α into letters of the new extended alphabet, we convert the fuzzy regular expression α to an ordinary regular expression α R . Then, starting from an arbitrary nondeterministic finite automaton A that recognizes the language ‖ α R ‖ represented by the regular expression α R , we construct fuzzy finite automata A α and A α r with the same or even less number of states than the automaton A , which recognize the fuzzy language ‖α‖ represented by the fuzzy regular expression α. The starting nondeterministic finite automaton A can be obtained from α R using any of the well-known constructions for converting regular expressions to nondeterministic finite automata, such as Glushkov–McNaughton–Yamadaʹs position automaton, Brzozowskiʹs derivative automaton, Antimirovʹs partial derivative automaton, or Ilie–Yuʹs follow automaton.