Chiusura prefissa del linguaggio

La chiusura prefissa di un linguaggio è un linguaggio composto dai prefissi di parole in un linguaggio L. $$ \bar{L} = \{ u \in E* : w \in L , u \preceq w \} $$

Generalmente il linguaggio L è un sottoinsieme dell'insieme dei prefissi.

$$ L \subseteq \bar{L} $$

Se il linguaggio dei prefissi ha la stessa cardinalità del linguaggio chiuso, allora il linguaggio è detto chiuso per prefissi.

$$ L = \bar{L} $$

Un esempio pratico

Il linguaggio L è composto da due parole

$$ L = \{ ape,oca \} $$

La chiusura prefissa di L è

$$ \bar{L} = \{ ε, a,ap,ape,o,oc,oca \} $$

Dove ε è la parola vuota.

Gli elementi della chiusura prefissa sono elementi dell'insieme delle parole.

Non necessariamente appartengono al linguaggio, né devono avere un significato.

E così via.