Date of Award
2011
Degree Type
Thesis
Degree Name
Master of Science
Program
Computer Science
Abstract
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.
Recommended Citation
Chowdhury, Jahedur Rahman, "State Complexity of Combined Operations on Finite Languages" (2011). Digitized Theses. 3508.
https://ir.lib.uwo.ca/digitizedtheses/3508