Linguaggio chiuso per prefisso
Cos'è la chiusura per prefisso
Un linguaggio L è chiuso per prefisso se per ciascuna parola w di L anche i prefissi della parola appartengono al linguaggio. E' indicato con un trattino in alto. $$ \bar{L} $$
La differenza tra linguaggi generati e accettati
In un automa a stati finiti deterministico (AFD) un linguaggio generato è sempre chiuso per prefisso.
Perché? Un linguaggio generato include tutte le parole che a partire dallo stato iniziale raggiungono uno stato qualsiasi dell'automa.
Ad esempio, la parola abcd fa parte del linguaggio generato L.
$$ w = abcd $$
La parola abcd ha i seguenti prefissi
$$ prefissi(w) = \{ abc, ab, a \} $$
I prefissi abc, ab, a fanno ancora parte del linguaggio generato perché raggiungono comunque uno stato dell'automa a partire dallo stato iniziale.
Il linguaggio accettato Lm non è necessariamente chiuso per prefisso.
Perché? Un linguaggio accettato include tutte le parole che a partire dallo stato iniziale raggiungono uno stato terminale. In questo caso i prefissi delle parole non fanno necessariamente parte del linguaggio accettato.
Ad esempio, la parola abcd fa parte del linguaggio accettato.
I prefissi abc, ab, a NON fanno parte del linguaggio accettato perché non raggiungono lo stato finale (d).
E così via.
