Normalizing Regular Expression by using Starred Trie Representation

Abstract

A regular expression is a set of characters that specify a pattern. A regular expression can be defined for every finite automaton, and is used for pattern matching. Here we are considering about normalized and un-normalized regular expression. Methodology has been developed to find out the normalized regular expression of a given un-normalized regular expression. Both normalized and un-normalized regular expression should be equivalent, means they should generate same strings over the given alphabets. Normalized regular expression is less time consuming in pattern matching as compare to un-normalized regular expression. Implementation of methodology is rule based and using starred trie representation. Implementation techniques for both methodologies are described in chapter 4 “Normalization of regular expression”. Both methodologies are developed in Java programming language. This thesis contains introduction of automaton, regular expression, literature review, problem statement, normalization techniqes, implementation environment followed by conclusion and future scope.