Construction of fuzzy automata from fuzzy regular expressions

被引:18
作者
Stamenkovic, Aleksandar [1 ]
Ciric, Miroslav [1 ]
机构
[1] Univ Nis, Fac Sci & Math, Nish 18000, Serbia
关键词
Fuzzy automata; Fuzzy regular expressions; Nondeterministic automata; Regular expressions; Position automata; State reduction; Right invariant equivalences; Lattice-ordered monoids; LATTICE-VALUED LOGIC; FORMAL POWER-SERIES; FINITE AUTOMATA; PARTIAL DERIVATIVES; MEMBERSHIP VALUES; PUMPING LEMMA; MINIMIZATION; REDUCTION; NFAS; DETERMINIZATION;
D O I
10.1016/j.fss.2012.01.007
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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 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 parallel to alpha(R)parallel to 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 parallel to alpha parallel to 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. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码:1 / 27
页数:27
相关论文
共 79 条