Linguaggio omega-regolare
# Linguaggio omega-regolare

I linguaggi ω-regolari sono una classe di ω-linguaggi che generalizzano i linguaggi regolari a parole di lunghezza infinita. Richard Büchi dimostrò nel 1962 che i linguaggi ω-regolari sono precisamente quelle definibili in una particolare logica monadica del secondo ordine chiamata S1S.

## Definizione formale

La definizione di linguaggio ω-regolare viene data ricorsivamente.

Un ω-linguaggio L è ω-regolare se è della forma:

* $A^{\omega }$, dove A è un linguaggio regolare non vuoto che non contiene la stringa vuota;
* $A\circ B$, dove è la concatenazione di un linguaggio regolare A e un linguaggio ω-regolare B (Notare che $B\circ A$ non è ben definito);
* $A\cup B$, dove A e B sono linguaggi ω-regolari.

Gli elementi di $A^{\omega }$ sono tutte le concatenazioni infinite di parole di $A$. Da notare che se $A$ è regolare, $A^{\omega }$non è necessariamente ω-regolare, poiché $A$ potrebbe essere $\{\epsilon \}$, l'insieme contenente unicamente la stringa vuota; in tal caso $A^{\omega }=A$, che non è un ω-linguaggio e quindi non ω-regolare.

## Equivalenza all'automa di Büchi

Resta da vedere quale tipo di automa riconosce le ω-espressioni, ossia tutte le espressioni regolari di lunghezza infinita appartenenti ad un linguaggio ω-regolare. La risposta è stata data da Richard Büchi con il suo automa.

Teorema: un linguaggio è riconosciuto da un automa di Büchi se e solo se è ω-regolare.

Dimostrazione: ogni linguaggio ω-regolare è riconosciuto da un automa di Büchi non deterministico. La dimostrazione si fa in maniera costruttiva: usando le proprietà di chiusura degli automi di Büchi e l'induzione strutturale sulla definizione di linguaggio ω-regolare, si può facilmente dimostrare che un automa di Büchi può essere costruito per ogni dato linguaggio ω-regolare.

Inversamente, per un dato automa di Büchi ${\mathcal {A}}=(Q,{\mathcal {F}},I,T)$, si costruisce un linguaggio ω-regolare e poi si mostra che questo linguaggio è riconosciuto da ${\mathcal {A}}$. Per una ω-espressione $w=a_{1}a_{2}\ldots$ sia $w(i,j)$ il segmento finito $a_{i+1}\ldots a_{j-1}a_{j}$ di $w$. Per ogni $q,q'\in Q$, si può definire un linguaggio regolare $L_{q,q'}$, che è accettato dall'automa finito $(Q,{\mathcal {F}},q,\{q'\})$.

Ne deriva che i linguaggi ω-regolari sono quelli costituiti dalle ω-espressioni accettata dagli automi di Büchi.

