State Complexity of Various Operations on Infix-free Regular Languages

Abstract

Regular languages are used in various 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 language can be described by regular expression or finite automata (deterministic or non-deterministic). Regular languages are of various types like infix free, prefix free, suffix free. These are used in various applications like pattern matching, computing forbidden words and text searching. The state complexity of an operation for regular languages is the number of states that are necessary and sufficient in the worst-case for the minimal deterministic finite-state automaton or non-deterministic finite automata that accepts the language obtained from the operation. For state complexity, we have to observe minimal state deterministic and non-deterministic models. For example, if the state complexity of the union of an m-state DFA language and an n-state DFA language is mn. It means that there exists two regular languages which are respectively accepted by an m-state DFA and an n-state DFA, such that their union is accepted by a mn-state DFA in the worst case. A regular language is infix-free if, for all distinct strings x, y ∈ Σ*, and x, y ∈ L imply that x and y are not substrings of each other. State complexity for deterministic and nondeterministic model in case of infix-free language have been determined. A software is designed for checking whether the language is infix-free or not.