system
Răspunde în limba română, în stilul Wikipedia, cat mai corect gramatical.
user
Dă-mi un rezumat despre Limbaj regulat.
assistant
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  (reuniunea),  (concatenarea) și  (închiderea Kleene) 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
 , 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 −1(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ă.

Limbaje formale și automate