Usuari:Mcapdevila/Llenguatge regular

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

Pot ser reconegut per:

• Un autòmat finit determinista
• Un autòmat finit no determinista
• Un autòmat de pila
• Un autòmat finit altern
• Una màquina de Turing de només lectura

És generat per:

• Una gramàtica regular
• Una gramàtica de prefixos

És descrit per:

• Una expressió regular

Llenguatges regulars sobre un alfabet

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 A ∪ B (unió), A • B (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> 0}és regular perquè pot ser representat, per exemple, mitjançant l'expressió regular a ⁺. El llenguatge L ={a ⁿ b ⁿ , 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

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ó L ∪ P de L i P
• La intersecció L ∩ P 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

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

uw ∈ L si i només si vw ∈ L 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

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

• 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)

• Llibre electrònic gratuït sobre autòmats i llenguatges formals (Tecnològic de Monterrei, Mèxic)