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.

Bibliografia

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