Lenguaiges regulares

Na teorie de la ciéncia de la cumputaçon i teorie formal de lenguaige, ua **lenguaige regular** ye ua lenguaige formal que puode ser spressa usando spressones regulares.
Note que ls recursos de las "spressones regulares" fornecidas cun bárias lenguaiges de porgramaçon son oumentada cun caratelísticas que las tornan capazes de recoincer lenguaiges que nun puoden ser spressas por spressones regulares formales (*cumo formalmente ye defenido ambaixo*).

Na hierarquia de chomsky, lenguaiges regulares son defenidas para ser lenguaiges que son geradas por gramáticas  tipo 3 (gramática regulares).
Lenguaiges regulares son mui úteles na análeze d'antradas i ne l porjeto dua lenguaige de porgramaçon.

## Defeniçon Formal
La coleçon de lenguaiges regulares subre un alfabeto Σ ye defenida recursibamente seguindo las regras ambaixo:
* La lenguaige bazie Ø ye ua lenguaige regular.
* La lenguaige cadeia bazie {ε} ye ua lenguaige regular.
* Para cada *la* ∈ Σ (*la* pertence la Σ), la lenguaige de l cunjunto unitairo {*la*} ye ua lenguaige regular.
* Se *La* i *B* son lenguaiges regulares, anton *La* ∪ *B* (ounion), *La* • *B* (cuncatenaçon), i *La** (Fecho de Klene ó streilha) son lenguaiges regulares.
* Nanhue outra lenguaige subre Σ ye regular.

Beija Spresson regular para ber la semántica i la síntaxe dessas ouparaçones. Note que ls causos arriba son cunsequéncias de las regras de la defeniçon de las spressones regulares.

;Eisemplos
To lenguaige fenita ye regular. Outros eisemplos típicos ancluen la lenguaige cunsistindo de todas las cadeias subre l'alfabeto {*la*,*b*} que cuntenhan un númaro par de *la*s, ó la lenguaige cunsistindo de todas las cadeias de la forma: bários *la*s seguido por bários *b*s.

Un simples eisemplo de lenguaige que nun ye regular ye l cunjunto de cadeias \{a^nb^n\,\vert\; n\ge 0\}. Esso porque nessa lenguaige, l númaro de *la*s cuntrola l númaro de *b*s, que nun son permitidos por qualquiera ua de las regras arriba. Ber mais an Lema de l bombeamiento para lenguaiges regulares.

## Eiquibaléncia cun outros formalismos
Ua lenguaige regular sastifaç las seguintes propiadades que son eiquibalentes:
* eilha puode ser aceita por un outómato fenito determinístico.
* eilha puode ser aceita por un outómato fenito nó-determinístico.
* eilha puode ser aceita por un outómato fenito altarnado.
* eilha puode ser gerada por ua gramática regular.
* eilha puode ser gerada por ua gramática de prefixos.
* eilha puode ser aceita por ua leitura de Máquina de Turing.
* eilha puode ser defenida nun monádico de la lógica de segunda orde.
* eilha ye l cunjunto eimaige dun subconjunto dun monóide fenito sob un homomorfismo de l monóide libre an sou alfabeto.
* eilha puode ser reconhecida por algua Monoide fenitamente gerada.

Las propiadades arriba son ousadas, ocasionalmente, cumo un defeniçon altarnatiba de las lenguaiges regulares.

## Resultados subre la Cumplexidade

Na teorie de la cumplexidade cumputacional, la classe de cumplexidade de todas lenguaiges regulares son ocasionalmente chamadas cumo **REGULAR** ó **REG** i eiquibale la DSPACE(L(1)), l  porblema de decison puode ser resolbido nun spácio custante (l spácio ousado ye andependiente de l tamanho de l'antrada). **REGULAR** ≠ '''AC'''<sup>0</sup>, ua beç que **REG** (trebialmente) cuntén l porblema de la paridade de detreminar se l númaro de bits 1 na antrada ye par ó ímpar i este porblema nun stá na**AC**0. An cuntrapartida, **REGULAR** nun cuntén **AC**0, porque las lenguaiges nun regular de ls palíndromos, ó la lenguagen nun regular \{0^m 1^m : m \in \mathbb N\}, ambas, puoden ser reconhecidas an **AC**0. 

Se ua lenguaige ye *nó* regular, eilha requer ua máquina que ne l mínimo &Omega;(log log *m*) de spácio para reconhecé-la (adonde *m* ye l tamaho de l'antrada). An outras palabras, DSPACE(L(log log *m*)) ye eiquibalente la classe de las lenguaiges regulares. Na prática, grande parte de las lenguaiges nun regulares son resolbidas por máquinas que tenga ne l mínimo spácio logarítmico.

## Propiadades de Fechamiento
Las lenguaiges regulares son cerradas subre bárias ouparaçones, ó seia, se ua lenguaige *K* i *L* son regulares, anton l resultado de las seguintes ouparaçones tamien ye regular:

* las ouparaçones teóricas de cunjunto: ounion K \cup L, anterseçon K \cap L, i cumplemiento \bar{L}. Por bias desso, defrença K-L tamien ye bálida, yá que ye cumpuosta pula anterseçon i pul cumplemiento.
* las ouparaçones regulares: ounion  K \cup L, cuncatenaçon K\circ L i streilha L^*.
* las ouparaçones de la família de lenguaiges abstratas: cadeia homomórfica, cadeia ambesa homomórfica, i anterseçon cun lenguaiges regulares. Cumo cunsequéncia, eilhas son cerradas sob arbitrária estados fenitos trasduçones, cumo quociente K/L cun ua lenguaige regular. Para alhá desso, las lenguaiges regulares son cerradas sob quocientes cun lénguas *arbitrárias*: Se L ye regular, anton L / K ye regular para qualquiera K.
* l reberso (ó eimaige spelhada) L^R.

## Decidindo se ua lenguaige ye regular

Al localizar las lenguaiges regulares na hierarquia de Chomsky, ouserbe que todas las lenguaiges regulares son libres de cuntesto. L cuntrairo yá nun ye berdadeiro: por eisemplo, ua lenguaige que cunsiste de todas las strings tenendo l mesmo 
númaro de *la*s i de *b*s ye libre de cuntesto mas nun ye regular. Para probar que  ua lenguaige cumo essa nun ye regular, usamos l Teorema de Myhill-Nerode ó l lema de l bombeamiento.

Eesiste dues aprossimaçones puramente algébricas que definen ua lenguaige regular. Se:
* Σ ye un alfabeto fenito,
* Σ* denota ua monoide libre subre Σ que ye cumpuosta por todas las cadeias formadas por Σ,
* *f* : Σ* → *M* ye ua monoide homomórfica adonde *M* ye ua monoide *fenita*,
* *S* ye un subconjunto de *M*
anton l cunjunto ye \{ w \in \Sigma^* \, | \, f(w) \in S \} ye regular. To lenguaige regular surge dessa forma.

Se *L* ye un subconjunto de Σ*, define-se la seguinte relaçon d'eiquibaléncia de ~ (coincida cumo relaçon sintática) subre Σ*: *u* ~ *b* 
ye defenida por : *uw* ∈ *L* se i solamente se *bw* ∈ *L* para to *w* ∈ Σ*.

La lenguaige *L* ye regular se i solamente se l númaro de classes eiquibalentes de ~  ye fenita (Ua proba desso ye fornecida ne l'artigo de la monoide sintática); se esse ye l causo, esse númaro ye eigual al númaro de stados dun outómato fenito determinístico mínimo qu'aceita *L*.

Un cunjunto similar de declaraçones puode ser formulado por ua monoide M\subset\Sigma^*. Nesse causo, l'eiquibaléncia subre *M* lieba al cunceito dua lenguaige reconhecible.

## Lenguaiges Finitas
Un subconjunto specífico de la classe de las lenguaiges regulares ye l cunjunto de las lenguaiges fenitas - aqueilhes que cunténen solo un númaro fenito de palabras. Essas lenguaiges son regulares, yá que ye possible criar ua spresson regular que ye la ounion de cada palabra de la lenguaige.

## L númaro de palabras dua lenguaige regular
Para qualquiera lenguaige L eisiste custantes \lambda_1,\,\ldots,\,\lambda_k i polinómios p_1(x),\,\ldots,\,p_k(x)
tal que para cada m l númaro s_L(m) de palabras de tamanho m an L sastifaç l'eiquaçon
s_L(m)=p_1(m)\lambda_1^m+\dotsb+p_k(m)\lambda_k^m. Assi, la nun regularidade d'alguas lenguaiges L' puoden ser probadas pula enumeraçon de las palabras an L'. Cunsidre, por eisemplo, la Lenguaige de Dyck de cadeias de parénteses balanceados. L númaro de palabras de tamanho 2n
na lenguaige Dyck ye eigual al númaro Catalan C_n\sim\frac{4^n}{n^{3/2}\sqrt{\pi}},l qual nun ye de la forma p(m)\lambda^m,
cumprobando la nun regularidade de la lenguaige de Dyck.

### Teorema de l'iteraçon para lenguaiges regulares

Se *L* ye ua lenguaige regular, anton eisiste un *m* tal que para to *x* &esin; *L* tal que |*x*| &ge; *m*, *x* puode ser rescrito de la forma *wyç*, |*y*| &le; *m*, i &forall; *i*, *i* &ge; 0 xy^{i}z &esin; *L*

## Beija tamien
* Lema de l bombeamiento para lenguaiges regulares
* Ounion de dues lenguaiges regulares

## Refréncias

*  Chater 1: Regular Languages, pp.31&ndash;90. Susection "Decidable Porblems Cuncerning Regular Languages" of section 4.1: Decidable Languages, pp.152&ndash;155.