Limbaj omega-regulat

Limbile Ω-regulate sunt o clasă de limbi ω care generalizează limbile regulate la cuvinte de lungime infinită. Richard Büchi a demonstrat în 1962 că limbajele ω-regulate sunt exact cele definibile într-o anumită logică monadică de ordinul doi numită S1S.

Definiție formală

Definiția limbajului ω-regulat este dată recursiv .

Un limbaj ω L este ω-regulat dacă are forma :

$A^{\omega }$ ${\ displaystyle A ^ {\ omega}}$ ${\ displaystyle A ^ {\ omega}}$ , unde A este un limbaj obișnuit care nu conține șirul gol;
$A\circ B$ ${\ displaystyle A \ circ B}$ ${\ displaystyle A \ circ B}$ , unde este concatenarea unui limbaj regulat A și a unui limbaj ω-regulat B (Rețineți că $B\circ A$ ${\ displaystyle B \ circ A}$ ${\ displaystyle B \ circ A}$ nu este bine definit);
$A\cup B$ ${\ displaystyle A \ cup B}$ $A \ cup B$ , unde A și B sunt languages-limbi regulate.

Elementele $A^{\omega }$ ${\ displaystyle A ^ {\ omega}}$ ${\ displaystyle A ^ {\ omega}}$ sunt toate concatenări infinite de cuvinte ale $LA$ ${\ displaystyle A}$ $LA$ . Rețineți că dacă $LA$ ${\ displaystyle A}$ $LA$ este regulat, $A^{\omega }$ ${\ displaystyle A ^ {\ omega}}$ ${\ displaystyle A ^ {\ omega}}$ nu este neapărat ω-regulat, deoarece $LA$ ${\ displaystyle A}$ $LA$ ar putea fi $\{\epsilon \}$ ${\ displaystyle \ {\ epsilon \}}$ ${\ displaystyle \ {\ epsilon \}}$ , setul care conține doar șirul gol; atunci $A^{\omega }=A$ ${\ displaystyle A ^ {\ omega} = A}$ ${\ displaystyle A ^ {\ omega} = A}$ , care nu este o limbă ω și, prin urmare, nu este ω-regulată.

Echivalența cu automatul Büchi

Rămâne de văzut ce tip de automat recunoaște expresiile ω, adică toate expresiile regulate de lungime infinită aparținând unui limbaj ω-regulat. Răspunsul a fost dat de Richard Büchi cu automatul său.

Teorema: un limbaj este recunoscut de un automat Büchi dacă și numai dacă este ω-regulat.

Dovadă : fiecare limbaj ω-regulat este recunoscut de un automat Büchi nedeterminist. Dovada se face într-un mod constructiv: folosind proprietățile de închidere ale automatelor Büchi și inducerea structurală pe definiția limbajului ω-regulat, se poate arăta cu ușurință că un automat Büchi poate fi construit pentru orice limbaj given-regulat dat.

Invers, pentru un automat Büchi dat ${\mathcal {A}}=(Q,{\mathcal {F}},I,T)$ ${\ displaystyle {\ mathcal {A}} = (Q, {\ mathcal {F}}, I, T)}$ ${\ displaystyle {\ mathcal {A}} = (Q, {\ mathcal {F}}, I, T)}$ , construim un limbaj ω-regulat și apoi arătăm că acest limbaj este recunoscut de ${\mathcal {A}}$ ${\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ . Pentru o expresie ω $w=a_{1}a_{2}\ldots$ ${\ displaystyle w = a_ {1} a_ {2} \ ldots}$ ${\ displaystyle w = a_ {1} a_ {2} \ ldots}$ este $w(i,j)$ ${\ displaystyle w (i, j)}$ ${\ displaystyle w (i, j)}$ segmentul terminat $a_{i+1}\ldots a_{j-1}a_{j}$ ${\ displaystyle a_ {i + 1} \ ldots a_ {j-1} a_ {j}}$ ${\ displaystyle a_ {i + 1} \ ldots a_ {j-1} a_ {j}}$ din $w$ ${\ displaystyle w}$ $w$ . Pentru fiecare $q,q'\in Q$ ${\ displaystyle q, q '\ în Q}$ ${\ displaystyle q, q '\ în Q}$ , se poate defini un limbaj obișnuit $L_{q,q'}$ ${\ displaystyle L_ {q, q '}}$ ${\ displaystyle L_ {q, q '}}$ , care este acceptat de automatul finit $(Q,{\mathcal {F}},q,\{q'\})$ ${\ displaystyle (Q, {\ mathcal {F}}, q, \ {q '\})}$ ${\ displaystyle (Q, {\ mathcal {F}}, q, \ {q '\})}$ .

Rezultă că limbile ω-regulate sunt cele constituite de expresiile accepted acceptate de automatele Büchi ^[1] .

Notă

^ (EN) E. Allen Emerson, The Role of Büchi Automata's in Computing Science , în Saunders Mac Lane și Dirk Siefkes (eds), The Collected Works of J. Richard Büchi, 1990, pp. 18-22, DOI : 10.1007 / 978-1-4613-8928-6 . Adus la 30 decembrie 2020 .

Bibliografie

( EN ) Ludwig Staiger, Languages-Languages , în G. Rozenberg și A. Salomaa (eds), Handbook of formal languages , Springer, 1997, pp. 339–387, ISBN 3-540-61486-9 ,OCLC 35762746 . Adus la 31 decembrie 2020 .
( EN ) Wolfgang Thomas, Automate on Infinite Objects , în Leeuwen, J. van (Jan) (editat de), Handbook of theory computer science , Amsterdam, Elsevier, 1990, pp. 133-192, ISBN 0-444-88075-5 ,OCLC 21563125 . Adus la 31 decembrie 2020 .

Portal IT

Portalul de matematică

[1] (EN) E. Allen Emerson, The Role of Büchi Automata's in Computing Science , în Saunders Mac Lane și Dirk Siefkes (eds), The Collected Works of J. Richard Büchi, 1990, pp. 18-22, DOI : 10.1007 / 978-1-4613-8928-6 . Adus la 30 decembrie 2020 .

[1]