Conversion of Deterministic Finite Automata to Regular Expression

Abstract

Regular expressions are well known in the field of computer science. They are widely used in the field of compilers, programming languages, pattern recognition, protocol conformance testing etc. There are various methods for the conversion of deterministic finite automata to regular expression like Transitive closure method, Brzozowski Algebraic method and state elimination method. State elimination method is the most widely used approach for converting deterministic finite automata to regular expression. There are many heuristics proposed by the researchers on the basis of which state elimination gives shorter regular expression. Yo Sub Han and Derick Wood introduced the concept of bridge state, vertical chopping and horizontal chopping for smaller regular expressions. We intend to find the smallest regular expression equivalent to a given deterministic finite automata. The thesis analyzes and compares different approaches used for conversion of DFA to RE and new heuristics are proposed for obtaining smaller regular expression corresponding to a given DFA. Researchers have proposed that removal of bridge states using state elimination method after the removal of non bridge states leads to shorter regular expression. The concept of bridge state is mathematically given but no formal algorithm is given. A formal algorithm for bridge state is proposed by which DFA can be converted into regular expression and the relation between the size of a regular expression and the size of the DFA is estimated.