Union-Free Decomposition of Regular Languages

Abstract

Regular expressions are well known in the field of computer science. They are commonly used and well-applicable in theory as well as in practice. The regular expressions are used in field of compilers, programming languages, pattern recognition, protocol conformance testing etc. There exists an algorithm for union-free decomposition of regular language. The algorithm uses a set of all maximal finite concatenations of languages. To construct a union-free decomposition, the algorithm examines all the subsets of maximal finite concatenations of languages and chooses the subset containing a minimum number of languages. By decomposing the regular language into an equivalent union-free regular language also helps in determining the union complexity of regular language. The unioncomplexity of a language is one if and only if it is union-free regular. An algorithm is proposed in this thesis report, for determining whether a regular language is union-free or not. The same is implemented in .NET. For decomposition of a regular expression into an equivalent union-free regular expression, an algorithm is proposed. Size relationship between non-union-free and equivalent union-free regular expression is also discussed.