State Complexity of Combined Operations for Suffix-free Regular Languages

Abstract

A regular expression is a pattern that describes a set of strings of particular type described by finite automata. Regular languages are classified into prefix-free, suffix-free, infix-free languages. Study of state complexity is strongly motivated by applications of finite automata in software engineering, programming languages, natural language, speech processing and other practical areas. Since many of these applications use automata of large sizes, it is important to know the size of automata which is defined by the number of states in the automata. Number of states in the DFA accepting the language defines the state complexity of languages. Recently researchers have studied the state complexities of prefix free regular languages for individual and combined operations and suffix-free regular languages for individual operations. This thesis focuses on estimating the state complexities of combined operations for suffixfree regular languages. iii