Date of Award


Degree Type


Degree Name

Master of Science


Computer Science


State complexity is a descriptive complexity measure for regular languages. It is a fundamental topic in automata and formal language theory. The state complexity of a regular language is the number of states in the minimal complete deterministic finite automaton accepting the language. During the last few decades, many publications have focused and studied the state complexity of many individual as well as combined operations on regular languages. Also, the state complexity of some basic operations on finite languages has been studied. But until now there has been no study on the state complexity of combined operations on finite languages.

In this thesis, we will first study the state complexity of the combined operation, star of union, on finite languages and give an exact bound. Then we will investigate the state complexity of star of catenation and show its approximation with a good ratio bound and finally, we will prove an upper bound for star of intersection.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.