Let $X$ be a set, and $w\in X^*$ be a word, i.e. an element of the free monoid on $X$ . A word $v\in X^*$ is called prefix of $w$ when a second word $z\in X^*$ exists such that $x=vz$ .

Note that the empty word $\varepsilon$ and $w$ are prefix of $w$ . The prefix set of $w$ is the set $\prefi(w)$ of prefixes of $w$ , i.e. if $w=w_1w_2...w_n$ with $w_j\in X$ for each $j\in\{1,...,n\}$ we have $$\prefi(w)=\{\varepsilon,\ w_1,\ w_1w_2,\ ... ,\ w_1w_2...w_{n-1},\ w\}.$$