Omega linguaggio

Un ω-linguaggio è un insieme di sequenze di simboli di lunghezza infinita.

Definizione formale

Sia un ω-linguaggio $L$ definito su un alfabeto Σ (non necessariamente finito). $L$ è quindi l'insieme delle parole di lunghezza infinita sull'alfabeto $\mathrm{\Sigma }$.

Seguendo la definizione standard della teoria dei linguaggi formali, ${\mathrm{\Sigma }}^{*}$ è l'insieme di tutte le parole finite su $\mathrm{\Sigma }$.

Si definisce quindi un ω-linguaggio $L$ come l'insieme di tutte le parole di lunghezza infinita $x\in {\mathrm{\Sigma }}^{\omega }$.

Dal punto di vista della notazione, l'insieme di tutte le parole infinite su $\mathrm{\Sigma }$ è indicato con ${\mathrm{\Sigma }}^{\omega }$. L'insieme di tutte le parole finite e infinite su $\mathrm{\Sigma }$ è talvolta scritto ${\mathrm{\Sigma }}^{\mathrm{\infty }}$.

Operatori

Vengono definiti sugli ω-linguaggi una serie di operatori.

• Intersezione e unione. Dati gli ω-linguaggi $L$ e $M$, sia $L\cup M$ che $L\cap M$ sono ω-linguaggi.
• Concatenazione sinistra. Sia $L$ un ω-linguaggio e $K$ un linguaggio di parole finite. Al fine di creare un nuovo ω-linguaggio concatenando i due linguaggi, $K$ può essere concatenato a sinistra unicamente a $L$ per produrre il nuovo ω-linguaggio $K\circ L$.
• Omega (iterazione infinita). L'operatore ^ω è la versione infinita dell'operatore stella di Kleene su linguaggi di lunghezza finita. Dato un linguaggio formale $L$, $L^{\omega }$ è l'ω-linguaggio fatto da tutte le sequenze infinite di parole da $L$.
• Prefisso. Sia w una ω-parola. Allora il linguaggio formale $Pref(w)$ contiene ogni prefisso finita di w.
• Limite. Dato un linguaggio finito $L$, una ω-parola w è nel limite di $L$ se e solo se $Pref(w)\cap L$ è un linguaggio infinito. In altre parole, per un numero naturale arbitrariamente grande n, è sempre possibile scegliere qualche parola di $L$, la cui lunghezza sia maggiore di n e che al tempo stesso sia anche un prefisso di w. L'operazione limite su $L$ può essere scritta $L^{\sigma }$ oppure $\overrightarrow{L}$.

Distanza tra ω-parole

L'insieme ${\mathrm{\Sigma }}^{\omega }$ può essere trasformato in uno spazio metrico definendo una metrica $d:{\mathrm{\Sigma }}^{\omega }\times {\mathrm{\Sigma }}^{\omega }\to ℝ$ tale che:

$d(w,v)=\inf \{2^{-|x|}:x\in {\mathrm{\Sigma }}^{*}\text{and}x\in \text{Pref}(w)\cap \text{Pref}(v)\}$

dove $|x|$ è interpretato come "la lunghezza di x" (numero di simboli in x ), e $\inf$ è l'estremo inferiore su un insieme di numeri reali. Se $w=v$ allora non esiste un prefisso x più lungo e $d(w,v)=0$. La relazione simmetrica è evidente. La transitività deriva dal fatto che se w e v hanno un prefisso condiviso massimo di lunghezza m e v e u hanno un massimo prefisso condiviso di lunghezza n, allora i primi $\min \{m,n\}$ caratteri di w e u devono essere gli stessi e quindi $d(w,u)\le 2^{-\min \{m,n\}}\le 2^{-m}+2^{-n}=d(w,v)+d(v,u)$ . Ciò mostra che d è una metrica.

Sottoclassi importanti

La sottoclasse più utilizzata degli ω-linguaggi è l'insieme dei linguaggi ω-regolari, che sono riconoscibili dagli automi di Büchi. Ne deriva che il problema decisionale dell'appartenenza di una stringa infinita ad un linguaggio ω-regolare è decidibile usando un automa di Büchi.

Bibliografia

• Template:Cita pubblicazione
• Template:Cita libro
• Template:Cita libro

Voci correlate

• Linguaggio ω-regolare