Linguaggio omega-regolare: differenze tra le versioni
m aggiunta Categoria:Teoria della computazione usando HotCat |
sez. Note |
||
Riga 21: | Riga 21: | ||
Inversamente, per un dato automa di Büchi <math>A=(Q,\Sigma, \Delta, I, F)</math>, si costruisce un linguaggio ω-regolare e poi si mostra che questo linguaggio è riconosciuto da ''A.'' Per una ω-espressione <math>w=a_1 a_2 \ldots</math> sia <math>w(i,j)</math> il segmento finito <math>a_{i+1}\ldots a_{j-1} a_j</math> di ''w'' . Per ogni <math>q,q' \in Q</math>, si può definire un [[linguaggio regolare]] <math>L_{q,q'}</math>, che è accettato dall'automa finito <math>(Q,\Sigma, \Lambda, q, \{q'\})</math>. |
Inversamente, per un dato automa di Büchi <math>A=(Q,\Sigma, \Delta, I, F)</math>, si costruisce un linguaggio ω-regolare e poi si mostra che questo linguaggio è riconosciuto da ''A.'' Per una ω-espressione <math>w=a_1 a_2 \ldots</math> sia <math>w(i,j)</math> il segmento finito <math>a_{i+1}\ldots a_{j-1} a_j</math> di ''w'' . Per ogni <math>q,q' \in Q</math>, si può definire un [[linguaggio regolare]] <math>L_{q,q'}</math>, che è accettato dall'automa finito <math>(Q,\Sigma, \Lambda, q, \{q'\})</math>. |
||
Ne deriva che i linguaggi ω-regolari sono quelli costituiti dalle ω-espressioni accettata dagli automi di Büchi. |
Ne deriva che i linguaggi ω-regolari sono quelli costituiti dalle ω-espressioni accettata dagli automi di Büchi<ref>{{Cita libro|capitolo=The Role of Büchi’s Automata in Computing Science|autore=E. Allen Emerson|pp= 18-22|titolo=The Collected Works of J. Richard Büchi |url=https://link.springer.com/book/10.1007/978-1-4613-8928-6 |accesso=2020-12-30 |data=1990 |lingua=en |DOI=10.1007/978-1-4613-8928-6|curatore=Saunders Mac Lane e Dirk Siefkes}}</ref>. |
||
== Note == |
|||
<references/> |
|||
== Bibliografia == |
== Bibliografia == |
Versione delle 17:47, 31 dic 2020
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 A. Per una ω-espressione sia il segmento finito di w . 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[1].
Note
- ^ (EN) E. Allen Emerson, The Role of Büchi’s Automata in Computing Science, in Saunders Mac Lane e Dirk Siefkes (a cura di), The Collected Works of J. Richard Büchi, 1990, pp. 18-22, DOI:10.1007/978-1-4613-8928-6. URL consultato il 30 dicembre 2020.
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.