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 $\Sigma$.

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

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

Dal punto di vista della notazione, l'insieme di tutte le parole infinite su $\Sigma$ è indicato con $\Sigma ^{\omega }$. L'insieme di tutte le parole finite e infinite su $\Sigma$ è talvolta scritto $\Sigma ^{\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 ${\vec {L}}$.

Distanza tra ω-parole

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

$d(w,v)=\inf\{2^{-|x|}:x\in \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)\leq 2^{-\min\{m,n\}}\leq 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

• (EN) Perrin, D. e Pin, J.E., Infinite words, in Pure and Applied Mathematics, vol. 141, Elsevier, 2004. URL consultato il 31 dicembre 2020.
• (EN) Ludwig Staiger, ω-Languages, in G. Rozenberg e A. Salomaa (a cura di), Handbook of formal languages, Springer, 1997, pp. 339–387, ISBN 3-540-61486-9, OCLC 35762746. URL consultato il 31 dicembre 2020.
• (EN) Wolfgang Thomas, Automata on Infinite Objects, in Leeuwen, J. van (Jan) (a cura di), Handbook of theoretical computer science, Amsterdam, Elsevier, 1990, pp. 133-192, ISBN 0-444-88075-5, OCLC 21563125. URL consultato il 31 dicembre 2020.

Voci correlate

• Linguaggio ω-regolare