Limbaj regulat

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\cup B$ (reuniunea), $A\cdot B$ (concatenarea) și $A^{*}$ (închiderea Kleene) sunt limbaje regulate.
• Nici un alt limbaj peste Σ nu este regulat.

Toate limbajele finite sunt regulate. Alte exemple tipice includ:

• $\{w\in \{a,b\}||w|_{a}\vdots 2\}$, limbajul constând din toate șirurile peste alfabetul {a, b} care conțin un număr par de a-uri
• $\{a^{n}b^{m}|n,m\in \mathbb {N} \}$, 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)) include 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/ Arhivat în 4 aprilie 2006, la Wayback Machine.. Un pachet software pentru manipularea expresiilor regulate, automatelor finite și limbajelor finite. Gratuit pentru utilizare necomercială.