Physical Sciences and Mathematics Commons^™

Advanced Topics On State Complexity Of Combined Operations, Yuan Gao

Electronic Thesis and Dissertation Repository

State complexity is a fundamental topic in formal languages and automata theory. The study of state complexity is also strongly motivated by applications of finite automata in software engineering, programming languages, natural language and speech processing and other practical areas. Since many of these applications use automata of large sizes, it is important to know the number of states of the automata. In this thesis, we firstly discuss the state complexities of individual operations on regular languages, including union, intersection, star, catenation, reversal and so on. The state complexity of an operation on unary languages is usually different from that …