Limbaje regulate

Un limbaj regulat este un limbaj formal (adică o mulţime posibil infinită de secvenţe finite de simboluri dintr-un alfabet finit) care satisface următoarele proprietăţi echivalente:

poate fi acceptat de un automat finit determinist
poate fi acceptat de un automat finit nedeterminist
poate fi acceptat de un automat finit alternant
poate fi descris de o expresie regulată
poate fi generat de o gramatică regulată
poate fi generat de o gramatică de prefixe
poate fi acceptat de o maşină Turing read-only
poate fi definit de o logică de ordinul 2 monadică

Limbaje regulate peste un alfabet

Colecţia limbajelor regulate peste un alfabet Σ se defineşte recursiv după cum urmează:

limbajul vid Ø este limbaj regulat.
Limbajul format din şirul vid { ε } este limbaj regulat.
Pentru fiecare a ∈ Σ, limbajul singleton { a } este limbaj regulat.
Dacă A şi B sunt limbaje regulate, atunci A U B (reuniunea), A • B (concatenarea) şi A* (Kleene star) sunt limbaje regulate.
Nici un alt limbaj peste Σ nu este regulat.

Toate limbajele finite sunt regulate. Alte exemple tipice includ limbajul constând din toate şirurile peste alfabetul {a, b} care conţin un număr par de a-uri, sau limbajul constând din toate şirurile de forma: câţiva de a urmaţi de mai mulţi b.

Dacă un limbaj nu este regulat, este nevoie de o maşină cu spaţiu de cel puţin O(log log n) pentru a-l recunoaşte (unde n este lungimea intrării). Cu alte cuvinte, DSPACE(o(log log n)) e egal cu clasa limbajelor regulate. În practică, majoritatea problemelor neregulate sunt rezolvate de maşini care folosesc cel puţin spaţiu logaritmic.

Proprietăţile de închidere

Rezultatele operaţiilor de reuniune, intersecţie şi diferenţă de mulţimi, când sunt aplicate pe limbaje regulate, sunt limbaje regulate; Complementul unui limbaj regulat peste alfabetul său este şi el limbaj regulat. Inversul fiecărui şir dintr-un limbaj regulat produce un alt limbaj regulat. Concatenarea a două limbaje regulate (în sensul concatenării fiecărui şir din primul limbaj cu fiecare şir din al doilea) este tot un limbaj regulat. Operaţia de amestecare, aplicată pe două limbaje regulate, produce alt limbaj regulat. Câtul la dreapta şi câtul la stânga al unui limbaj regulat la un alt limbaj oarecare este tot limbaj regulat.

Identificarea unui limbaj regulat

Pentru a localiza limbajele regulate în ierarhia Chomsky, observăm că fiecare limbaj regulat este independent de context. Inversa nu este adevărată: de exemplu limbajul costând din toate şirurile care au acelaşi număr de a-uri şi b-uri este independent de context dar nu este regulat. Pentru a demonstra că un astfel de limbaj nu este regulat, se utilizează teorema Myhill-Nerode sau lema de pompare.

Există două abordări pur algebrice în definirea limbajelor regulate. Dacă Σ este un alfabet finit şi Σ* este monoidul liber peste Σ constând din toate şirurile peste Σ, f : Σ* → M este un omomorfism de monoizi unde M este un monoid finit, şi S este o submulţime a lui M, atunci mulţimea f⁻¹(S) este limbaj regulat. Toate limbajele regulate apar în această manieră.

Dacă L este o submulţime a lui Σ*, se defineşte o relaţie de echivalenţă ~ peste Σ* după cum urmează: u ~ v se defineşte ca fiind

uw ∈ L dacă şi numai dacă vw ∈ L pentru toate w ∈ Σ*

Limbajul L este regulat dacă şi numai dacă numărul claselor de echivalenţă ale lui ~ este finit; dacă este aşa, acest număr este egal cu numărul de stări ale automatului finit determinist minimal care acceptă limbajul L.

Bibliografie

Michael Sipser - "Introduction to the Theory of Computation", PWS Publishing, 1997, ISBN 0-534-94728-X, Capitolul 1: Regular Languages, pp.31–90. Subsecţiunea "Decidable Problems Concerning Regular Languages" din secţiunea 4.1: Decidable Languages, pp.152–155.

Resurse externe

Departmentul de Informatică de la University of Western Ontario: Grail+, http://www.csd.uwo.ca/Research/grail/. Un pachet software pentru manipularea expresiilor regulate, automatelor finite şi limbajelor finite. Gratuit pentru utilizare necomercială.

Informatică | Limbaje formale şi automate

Gourt Home::Gourt :: Limbaje regulate