Closure Properties of Prefix-Free and Suffix-Free Regular Languages

Abstract

Regular languages are specified by finite-state automata (FAs) or regular expressions. Regular languages are used in diverse fields of computer science like compilers, data compression, text processing, software engineering and pattern matching. Language can be categorized as regular, context free, context sensitive or recursive enumerable based on Chomsky hierarchy for languages. Regular languages can be classified as infix free, prefix free, suffix free. These are used in various applications like pattern matching, computing forbidden words and text searching. 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. A regular language is prefix-free if and only if its minimal DFA M has only one final state and the final state has no out transitions whose target state is not a sink state. A regular language is suffix-free if and only if its minimal DFA M have a exclusive sink state and its starting state does not have any in-transitions.This thesis specifies that in prefix-free and suffix-free regular languages under what operation languages are closed.