From Wikipedia, the free encyclopedia
En matemàtiques, lògica i complexitat computacional un llenguatge formal és un llenguatge regular si es pot expressar usant expressions regulars.[1][2][3]
També es pot definir un llenguatge regular com aquell que reconeix un autòmat finit. L'equivalència entre les expressions regulars i autòmats finits es demostra al teorema de Kleene. Aquest tipus de llenguatges s'etiqueten com de tipus 3 en la jerarquia de Chomsky dels llenguatges formals.
Els llenguatges regulars son força útils en l'anàlisi d'entrades i el disseny de llenguatges de programació.
La col·lecció de llenguatges regulars sobre un alfabet Σ es defineix recursivament com:
Veieu Expressio regular per la seva sintaxi i semàntica.
Tots els llenguatges finits son regulars. En particular el llenguatge buit {ε} = Ø és regular. Altres exemples típics consisteixen en el llenguatge format per totes les cadenes sobre un alfabet {a, b} que contenen un nombre parell de as o el llenguatge consistent en totes les cadenes de les formes: moltes as seguides de moltes bs.
Un exemple senzill d'un llenguatge que no és regular és el conjunt de cadenes tal que { anbn | n ≥ 0 }. Intuïtivament es veu que no es pot reconèixer amb un autòmat finit, ja que té una memòria finita i no pot recordar el nombre exacte d'as.[4]
Un llenguatge regular satisfà les següents propietats equivalents:
Els llenguatges regulars son tancats segons vàries operacions. Si els llenguatges K i L son regulars, també ho serà el resultat de les operacions següents:
Donats dos autòmats finits deterministes A i B, és decidible saber si accepten el mateix llenguatge.[5] Com a conseqüència, usant les propietats de clausura, els següents problemes també son decidibles per qualsevol autòmat finit A i B, que accepten els llenguatges LA i LB respectivament:
Per expressions regulars, el problema d'universalitat és NP-complet inclús per un alfabet simple.[6] Per alfabets més grans, el problema és PSPACE-complet.[7][8]
En complexitat computacional, la classe de complexitat de tots els llenguatges regulars s'anomena sovint com REGULAR o REG i és equivalent a DSPACE (O (1)), és a dir, el conjunt de problemes de decisió que es poden resoldre en espai constant (l'espai utilitzat és independent de la mida d'entrada).
REGULAR ≠ AC0, ja que conté el problema de paritat de determinar si el nombre de bits a 1 a l'entrada és parell o senar, i aquest problema no està a AC0.
D'altra banda, REGULAR no conté AC0, ja que el llenguatge no regular dels palíndroms, o el llenguatge no regular es poden reconèixer per AC0.[9]
Si un llenguatge es no regular, requereix que una màquina amb almenys espai Ω(log log n) per reconèixer-lo. Dit d'altra manera, la classe DSPACE (o(log log n)) és igual a la classe dels llenguatges regulars.[10]
Per trobar la posició dels llenguatges regulars dins de la jerarquia de Chomsky cal notar que tot llenguatge regular és lliure del context. A l'inrevés no és cert: per exemple el llenguatge consistent en totes les cadenes que tenen el mateix nombre d'as i de bs és lliure del context però no és regular. Per provar que un llenguatge d'aquest tipus no és regular es fa servir el teorema de Myhill-Nerode o el Lema de bombament.[11]
Els llenguatges regulars tenen subclasses força importants: