Some Improvements in the Construction of Fuzzy Automata

Abstract

Regular expression is a mathematical representation of regular language. There are many recent developments in Science, Engineering, and Mathematics in the previous century. In formal languages, string is either totally accepted or rejected, whereas in case of fuzzy languages, the string is not totally accepted or rejected, rather it belongs to the language with some degree of membership. One of the main concerns related to these developments is uncertainty. For handling uncertainty and reducing the gap between natural and programming language, the concept of fuzzy languages have been introduced as an extension of formal languages. Fuzzy automata are generalization of the classical automata, closing the gap between classical automata theory and natural languages. Fuzzy regular expressions and fuzzy automata have received significant attention due to their practical applications in various fields, such as databases, pattern recognition, control systems, discrete event systems, clinical monitoring, computing with words, learning systems, and descriptions of natural and programming languages. The main aim of this dissertation is to propose some improvements in the construction of fuzzy automata. The inclusion of shuffle operators in the regular expression is known as a parallel regular expression. Motivated by the applications of fuzzy automata and parallel regular expressions, we have proposed a new mathematical model that involves fuzziness in parallel finite automata. In this thesis, an algorithm is proposed for the conversion of parallel fuzzy regular expressions to ε-free fuzzy automata. Motivated by the existing literature for the transformation of finite automata to regular expression using approaches such as Arden’s Theorem, Transitive closure, Brzozowski algebraic and State removal, in this thesis, an algorithm is proposed for the conversion of a fuzzy automaton into a fuzzy regular expression by extending the well-known concept of the Transitive closure method. Furthermore, we have proved the equivalence of fuzzy automata and fuzzy regular expressions. Sempere introduced the concept of linear expressions to represent the linear context-free languages. Motivated by the existing work of Sempere, we have applied the concept of linear expressions for representing Inverted Repeats, Hairpin structures, Stem and Loop structures. Further, we have proposed the concept of fuzzy linear expressions. An algorithm is proposed for the conversion of fuzzy linear grammar to fuzzy linear expressions. At last, we have extended the concept of Antimirov’s partial derivatives for the conversion of fuzzy linear expressions to fuzzy automata. Keywords: Fuzzy regular expression, Fuzzy automata, Shuffle operator, Partial derivative, Two-sided partial derivative, Fuzzy linear expressions, Fuzzy context-free grammar.