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:

, dove A è un linguaggio regolare non vuoto che non contiene la stringa vuota; , dove è la concatenazione di un linguaggio regolare A e un linguaggio ω-regolare B (Notare che non è ben definito); , dove A e B sono linguaggi ω-regolari.

Gli elementi di sono tutte le concatenazioni infinite di parole di . Da notare che se è regolare, non è necessariamente ω-regolare, poiché potrebbe essere , l'insieme contenente unicamente la stringa vuota; in tal caso , 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 , si costruisce un linguaggio ω-regolare e poi si mostra che questo linguaggio è riconosciuto da . Per una ω-espressione sia il segmento finito di . Per ogni , si può definire un linguaggio regolare , che è accettato dall'automa finito .

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

Note

Bibliografia

Categoria:Teoria dei linguaggi formali Categoria:Teoria della computazione