Omega linguaggio

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

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

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

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

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

Vengono definiti sugli ω-linguaggi una serie di operatori.

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

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

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

dove ${\displaystyle |x|}$ è interpretato come "la lunghezza di x" (numero di simboli in x ), e ${\displaystyle \inf }$ è l'estremo inferiore su un insieme di numeri reali. Se ${\displaystyle w=v}$ allora non esiste un prefisso x più lungo e ${\displaystyle 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 ${\displaystyle \min\{m,n\}}$ caratteri di w e u devono essere gli stessi e quindi ${\displaystyle 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.

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.

• (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.

• Linguaggio ω-regolare

Portale Informatica

Portale Matematica