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 $\{ϵ\}$, 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 $𝒜=(Q,ℱ,I,T)$, si costruisce un linguaggio ω-regolare e poi si mostra che questo linguaggio è riconosciuto da $𝒜$. Per una ω-espressione $w=a_1{a}_2\dots$ sia $w(i,j)$ il segmento finito $a_{i+1}\dots a_{j-1}{a}_j$ di $w$. Per ogni $q,q^{\prime }\in Q$, si può definire un linguaggio regolare $L_{q,q^{\prime }}$, che è accettato dall'automa finito $(Q,ℱ,q,\{q^{\prime }\})$.

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

Bibliografia

• Template:Cita libro
• Template:Cita libro