Limbaj regulat

În informatică teoretică, un limbaj regulat este un limbaj formal , adică constând dintr-un set de șiruri construite cu un alfabet finit, care este descris printr-o expresie regulată , generată de o gramatică generativă regulată (sau de tip 3, conform ierarhiei Chomsky ) sau acceptat de un automat cu stare finită ( automat finit determinist sau automat cu stare finită nedeterminist ).

Limbi regulate bazate pe un alfabet

Setul de limbi obișnuite bazate pe un alfabet $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ este definit recursiv după cum urmează:

limbă goală $\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$ este un limbaj obișnuit.
limba $\left\{\epsilon \right\}$ ${\ displaystyle \ left \ {\ epsilon \ right \}}$ ${\ displaystyle \ left \ {\ epsilon \ right \}}$ conținând doar șirul gol este un limbaj obișnuit.
pentru fiecare personaj $a\in \Sigma$ ${\ displaystyle a \ in \ Sigma}$ ${\ displaystyle a \ in \ Sigma}$ , limba singleton $\left\{a\right\}$ ${\ displaystyle \ left \ {a \ right \}}$ $\ left \ {a \ right \}$ este un limbaj obișnuit.
de sine $LA$ ${\ displaystyle A}$ $LA$ Și $B.$ ${\ displaystyle B}$ $B.$ atunci sunt limbi obișnuite $A\cup B$ ${\ displaystyle A \ cup B}$ $A \ cup B$ , $A\circ B$ ${\ displaystyle A \ circ B}$ ${\ displaystyle A \ circ B}$ , Și $A^{*}$ ${\ displaystyle A ^ {*}}$ ${\ displaystyle A ^ {*}}$ sunt limbi obișnuite.
nicio altă limbă activată $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ este regulat.

Toate limbile limitate sunt regulate. Un alt exemplu tipic include limba care constă din toate șirurile alfabetului $\left\{a,b\right\}$ ${\ displaystyle \ left \ {a, b \ right \}}$ ${\ displaystyle \ left \ {a, b \ right \}}$ și care conține un număr par de a sau limba constând din toate șirurile de formă: zero sau mai mult a urmat de zero sau mai mult b .

Proprietăți de închidere

Limbile obișnuite sunt închise în ceea ce privește următoarele operațiuni:

${\bar {L}}$ ${\ displaystyle {\ bar {L}}}$ ${\ displaystyle {\ bar {L}}}$ completa
$L^{*}$ ${\ displaystyle L ^ {*}}$ ${\ displaystyle L ^ {*}}$ steaua lui kleene
$L_{1}\circ L_{2}$ ${\ displaystyle L_ {1} \ circ L_ {2}}$ ${\ displaystyle L_ {1} \ circ L_ {2}}$ concatenare
$L_{1}\cup L_{2}$ ${\ displaystyle L_ {1} \ cup L_ {2}}$ ${\ displaystyle L_ {1} \ cup L_ {2}}$ Uniune
$L_{1}\cap L_{2}$ ${\ displaystyle L_ {1} \ cap L_ {2}}$ ${\ displaystyle L_ {1} \ cap L_ {2}}$ intersecție
$L_{1}\smallsetminus L_{2}$ ${\ displaystyle L_ {1} \ smallsetminus L_ {2}}$ ${\ displaystyle L_ {1} \ smallsetminus L_ {2}}$ diferență
$L_{1}^{R}$ ${\ displaystyle L_ {1} ^ {R}}$ ${\ displaystyle L_ {1} ^ {R}}$ reflex

Probleme legate de limbile obișnuite

În ierarhia Chomsky, limbile regulate corespund limbajelor generate de gramaticile de tip 3 . Este posibil să se stabilească dacă un limbaj este regulat sau nu utilizând teorema Myhill-Nerode . În schimb, este posibil să se demonstreze că un limbaj nu este regulat folosind lema de pompare pentru limbi obișnuite .

Având două limbi obișnuite $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ și $L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ puteți verifica includerea $L_{1}\subseteq L_{2}$ ${\ displaystyle L_ {1} \ subseteq L_ {2}}$ ${\ displaystyle L_ {1} \ subseteq L_ {2}}$ folosind proprietățile de închidere. Din acest motiv, este posibil să se stabilească dacă două limbi regulate sunt echivalente.

Abordarea algebrică

Există două abordări algebrice pure pentru a defini limbaje regulate. De sine $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ este un alfabet finit e $\Sigma ^{*}$ ${\ displaystyle \ Sigma ^ {*}}$ $\ Sigma ^ {{*}}$ denotă monoidul liber pe $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ constând din toate șirurile $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ , $f:\Sigma ^{*}\rightarrow M$ ${\ displaystyle f: \ Sigma ^ {*} \ rightarrow M}$ ${\ displaystyle f: \ Sigma ^ {*} \ rightarrow M}$ este un homomorfism al monoidului unde $M.$ ${\ displaystyle M}$ $M.$ este un monoid finit , e $S.$ ${\ displaystyle S}$ $S.$ este un subset de $M.$ ${\ displaystyle M}$ $M.$ , unde funcția inversă $f^{-1}(S)$ ${\ displaystyle f ^ {- 1} (S)}$ ${\ displaystyle f ^ {- 1} (S)}$ este regulat. Fiecare limbă obișnuită vine în această formă.

De sine $L$ ${\ displaystyle L}$ $L$ este un subset de $\Sigma ^{*}$ ${\ displaystyle \ Sigma ^ {*}}$ $\ Sigma ^ {{*}}$ , se poate defini o relație de echivalență $\sim$ ${\ displaystyle \ sim}$ $\ sim$ în $\Sigma ^{*}$ ${\ displaystyle \ Sigma ^ {*}}$ $\ Sigma ^ {{*}}$ după cum urmează: $u\sim v$ ${\ displaystyle u \ sim v}$ ${\ displaystyle u \ sim v}$ este definit

uw\in L\iff vw\in L{\mbox{ per ogni }}w\in \Sigma ^{*}

{\ displaystyle uw \ in L \ if vw \ in L {\ mbox {pentru fiecare}} w \ in \ Sigma ^ {*}}

{\ displaystyle uw \ in L \ if vw \ in L {\ mbox {pentru fiecare}} w \ in \ Sigma ^ {*}}

Limba $L$ ${\ displaystyle L}$ $L$ este regulat dacă și numai dacă numărul de clase echivalente de $\sim$ ${\ displaystyle \ sim}$ $\ sim$ s-a terminat; în acest caz, acest număr este egal cu numărul stărilor celui mai puțin determinist automat finit pe care îl acceptă $L$ ${\ displaystyle L}$ $L$ .

Bibliografie

Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, Limbaje de modelare a complexității, Milano, Franco Angeli Editore, 2003, ISBN 88-464-4470-1 .
( EN ) language regular , în Academic Press Dictionary of Science and Technology , Oxford, Elsevier Science & Technology, 1992.
( EN ) John E. Hopcroft , Rajeev Motwani; Jeffrey D. Ullman , Expresii și limbi regulate , în Introducere în teoria automatelor, limbi și calcul , Addison Wesley, 15 iulie 2006, ISBN 978-0-321-46225-1 .
(EN) Martin Davis , Ron Sigal; Elaine J. Weyuker, Regular Languages , in Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science , Morgan Kaufmann, 17 februarie 1994, ISBN 978-0-12-206382-4 .

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere în limbă obișnuită

linkuri externe

( EN ) Grail + , pe grailplus.org , Universitatea din Western Ontario (arhivat din original la 18 octombrie 2016) .
(EN) jflap pe jflap.org, Universitatea Duke .

Teoria automatelor : limbaje formale și gramatici formale
Ierarhia Chomsky	Gramatica formală	Limba	Automat minim
Tipul-0	(nelimitat)	Recursiv enumerabil	Mașină Turing
	(nelimitat)	Recursiv	Decider
Tipul 1	Context dependent	Context dependent	Automat liniar
Tipul 2	Fără context	Fără context	Automat cu baterie ND
Tipul 3	Regulat	Regulat	Stări finite
Fiecare categorie de limbă sau gramatică este un subset adecvat al categoriei imediat deasupra acesteia.

Portal IT : accesați intrările Wikipedia care se ocupă cu IT