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.

La definizione di linguaggio ω-regolare viene data ricorsivamente.

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

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

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

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

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

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

Portale Informatica

Portale Matematica