Usuari:Mcapdevila/Llenguatge regular

De Viquipèdia
Dreceres ràpides: navegació, cerca

Un llenguatge regular és un tipus de llenguatge formal que satisfà les següents propietats:

Pot ser reconegut per:

És generat per:

És descrit per:

Llenguatges regulars sobre un alfabet[modifica | modifica el codi]

Un llenguatge regular sobre un alfabet  \Sigma donat es defineix recursivament com:

  • El llenguatge buit  \varnothing és un llenguatge regular
  • El llenguatge cadena buida{ε}és un llenguatge regular
  • Per a tot símbol a ∈  \Sigma {a}és un llenguatge regular
  • Si A i B són llenguatges regulars llavors AB (unió), AB (concatenació) i A * (clausura o estrella de Kleene) són llenguatges regulars
  • Si A és un llenguatge regular llavors ( A ) és el mateix llenguatge regular
  • No existeixen més llenguatges regulars sobre  \Sigma

Tot llenguatge formal finit constitueix un llenguatge regular. Altres exemples típics són totes les cadenes sobre l'alfabet{a, b}que contenen un nombre parell de aes o el llenguatge que consisteix en diverses aes seguides de diverses bes.

Si un llenguatge no és regular requereix una màquina amb almenys una complexitat de Ω (log log n) (on n és la mida de l'entrada). A la pràctica la majoria dels problemes no regulars són resolts amb una complexitat logarítmica.

Un llenguatge formal infinit pot ser regular o no regular. El llenguatge L ={a n , n> 0}és regular perquè pot ser representat, per exemple, mitjançant l'expressió regular a +. El llenguatge L ={a n b n , n> 0}és un llenguatge no regular atès que no és reconegut per cap de les formes de representació anteriorment enumerades.

Propietats de tancament[modifica | modifica el codi]

Els llenguatges regulars són tancats amb les següents operacions, de manera que si L i P són llenguatges regulars els següents llenguatges també seran regulars:

  • El complement  \bar{'' L ''} de L
  • La clausura o estrella de Kleene L * de L
  • El homomorfisme φ ( L ) de L
  • La concatenació L·P de L i P
  • La unió LP de L i P
  • La intersecció LP de L i P
  • La diferència L \ P de L i P
  • El revers L R de L

Decidir quan un llenguatge és regular[modifica | modifica el codi]

Per situar els llenguatges regulars en la jerarquia de Chomsky cal notar que tot llenguatge regular és també un llenguatge lliure de context, encara que l'afirmació contrària no és certa, per exemple: el llenguatge que conté el mateix nombre de aes i de bes és lliure de context però no regular. Per provar que un llenguatge d'aquest tipus no és regular s'usa el teorema de Myhill-Nerode, o el lema de bombament per exemple.

Hi ha dues aproximacions purament algebraiques per definir llenguatges regulars. Si  \Sigma és un alfabet finit i  \Sigma * és un monoide lliure consistent en totes les cadenes sobre  \Sigma , f:  \Sigma * → M és un monoide simètric on M és un monoide finit i S és un subconjunt de M llavors el conjunt f -1 (S) és regular. Tot llenguatge regular es presenta d'aquesta manera.

Si L és un subconjunt de Σ *, es defineix la relació equivalent # a Σ * de la següent manera: o # v significa

uwL si i només si vwL per a tot w ∈ Σ *

El llenguatge L és regular si i només si el nombre de classes d'equivalència de # és finit, si aquest és el cas, aquest nombre és igual al nombre d'estats de l'autòmat determinista mínim que reconeixerà L .

Llenguatges finits[modifica | modifica el codi]

Un subconjunt especial dels llenguatges regulars és el dels llenguatges finits, aquells que només contenen un nombre finit de paraules. Aquests són llenguatges òbviament regulars i un podria crear expressions regulars que serien la unió de totes les paraules del llenguatge que definirien aquest llenguatge.


Enllaços externs[modifica | modifica el codi]

  • Chalchaleros ! [Chalchaleros|http://www.ucse.edu.ar/fma/sepa/chalchalero.htm.] Programari visual gratuït per treballar amb llenguatges regulars, expressions regulars, gramàtiques regulars i autòmats finits. Projecte SEPA ! (Universitat Catòlica de Santiago de l'Estero)

Nota[modifica | modifica el codi]