Computer Science – Formal Languages and Automata Theory
Scientific paper
2011-05-31
Computer Science
Formal Languages and Automata Theory
26 pages, submitted to a journal
Scientific paper
Li and Pedrycz [Y. M. Li, W. Pedrycz, Fuzzy finite automata and fuzzy regular expressions with membership values in lattice ordered monoids, Fuzzy Sets and Systems 156 (2005) 68--92] 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 effective method for constructing an equivalent fuzzy finite automaton from a given fuzzy regular expression. In this paper we provide such an effective method. Transforming scalars appearing in a fuzzy regular expression {\alpha} into letters of the new extended alphabet, we convert the fuzzy regular expression {\alpha} to an ordinary regular expression {\alpha}_{R}. Then, starting from an arbitrary nondeterministic finite automaton A that recognizes the language ||{\alpha}_R|| represented by the regular expression {\alpha}_R, we construct fuzzy finite automata A_{\alpha} and A_{\alpha}^r with the same or even less number of states than the automaton A, which recognize the fuzzy language ||{\alpha}|| represented by the fuzzy regular expression {\alpha}. The starting nondeterministic finite automaton A can be obtained from {\alpha}_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.
Ćirić Miroslav
Stamenković Aleksandar
No associations
LandOfFree
Construction of fuzzy automata from fuzzy regular expressions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Construction of fuzzy automata from fuzzy regular expressions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Construction of fuzzy automata from fuzzy regular expressions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-337780