prefixclosure

Prefix closure, or prefixclosure, is a concept in formal languages. For a language L that is a subset of Σ*, the prefix closure Pref(L) is the set of all prefixes of strings in L. Formally, Pref(L) = { w ∈ Σ* | ∃ v ∈ Σ* with w v ∈ L }. Equivalently, Pref(L) consists of every finite initial segment of any string in L. The empty string ε is a prefix of every nonempty string, so ε ∈ Pref(L) whenever L ≠ ∅. If L is empty, Pref(L) = ∅.

Examples help illustrate the idea. If L = { a^n | n ≥ 0 }, then Pref(L) = a*, the set of all strings of a’s (including ε). If L = { ab, aabb, aaabbb, … } = { a^n b^n | n ≥ 1 }, Pref(L) contains strings such as a^i and a^i b^j with j ≤ i, for some n, and in particular includes ε and ab.

Properties and constructions. If L is a regular language, then Pref(L) is also regular. A standard construction uses a deterministic finite automaton for L: let R be the set of states from which a final state is reachable. The set of strings that lead from the start state to any state in R forms a regular language recognizing Pref(L). Consequently, Pref(L) can be recognized by a finite automaton obtained by marking R as accepting. If L is prefix-closed (every prefix of a word in L is also in L), then Pref(L) = L; not all languages are prefix-closed (for example, { a^n b^n | n ≥ 1 } is not).

Applications. Prefix closures are used to analyze extendability of partially read inputs, to study prefix-closed properties of languages, and in parsing and model checking where the prefixes of accepted strings are relevant. See also prefix-closed languages and regular languages.