Please use this identifier to cite or link to this item:
Title: Union-Free Decomposition of Regular Languages
Authors: Ghuman, Sukhpal Singh
Supervisor: Loura, Ajay Kumar
Keywords: Regular expression;union-free decomposition
Issue Date: 7-Aug-2012
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.
Appears in Collections:Masters Theses@CSED

Files in This Item:
File Description SizeFormat 
1829.pdf1.17 MBAdobe PDFThumbnail

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.