Conversion of Deterministic Finite Automata to Regular Expression Using Bridge State

Abstract

Regular expressions are widely used in the field of compiler design, text editor, search for an email- address, grep filter of unix, train track switches, pattern matching ,context switching and in many areas of computer science. The demand of smaller regular expression motivates research into the conversion of deterministic finite automta to regular expression for obtaining smaller regular expression. For conversion of deterministic finite automata to regular expression, several techniques like Transitive closure method, Brzozowski Algebraic method and state elimination method have been proposed. None of the above specified technique is able to find smallest regular expression. Our purpose is to find the smallest regular expression equivalent to given deterministic finite automata. State elimination approach is the most widely used and efficient approach for converting deterministic finite automata to regular expression. In order to choose optimal removing sequence of states in state elimination method for obtaining smaller regular expression, some heuristics like Delgado and Morais‟s state weight heuristic and Yo-Sub Han and Derick Wood‟s concept of bridge state, vertical chopping and horizontal chopping have been proposed. The presented thesis investigates and compares different techniques used for converting deterministic finite automata to regular expression. Brief comparisons amongst different techniques are presented and several heuristics are explored for obtaining smaller regular expression using state elimination approach. In order to obtain smaller regular expression using state elimination method optimal removal sequence of states should be chosen. For choosing optimal removal sequence of states new heuristics have been proposed in this thesis work. The software has been designed for conversion of deterministic finite automata to regular expression using newly developed heuristics.