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 las, ó la lenguaige cunsistindo de todas las cadeias de la forma: bários las seguido por bários bs.

Un simples eisemplo de lenguaige que nun ye regular ye l cunjunto de cadeias . Esso porque nessa lenguaige, l númaro de las cuntrola l númaro de bs, 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 ≠ AC0, 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á naAC0.M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-eiquipa hierarchy. Math. Systems Theory, 17:13–27, 1984. An cuntrapartida, REGULAR nun cuntén AC0, porque las lenguaiges nun regular de ls palíndromos, ó la lenguagen nun regular , ambas, puoden ser reconhecidas an AC0. 

Se ua lenguaige ye nó regular, eilha requer ua máquina que ne l mínimo Ω(log log m) de spácio para reconhecé-la (adonde m ye l tamaho de l'antrada).J. Hartmanis, P. L. Lewis II, and R. I. Stearnes. Hierarchies of memory-lemited cumputationes. Procedings of the 6th Annual IEEE Symposiun on Switching Circuit Theory and Logic Zeign, pp. 179–190. 1965. 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 , anterseçon , i cumplemiento . Por bias desso, defrença  tamien ye bálida, yá que ye cumpuosta pula anterseçon i pul cumplemiento.
 las ouparaçones regulares: ounion  , cuncatenaçon  i streilha .
 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  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) .

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  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 . 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  eisiste custantes  i polinómios 
tal que para cada  l númaro  de palabras de tamanho  an  sastifaç l'eiquaçon
. Assi, la nun regularidade d'alguas lenguaiges  puoden ser probadas pula enumeraçon de las palabras an . Cunsidre, por eisemplo, la Lenguaige de Dyck de cadeias de parénteses balanceados. L númaro de palabras de tamanho 
na lenguaige Dyck ye eigual al númaro Catalan ,l qual nun ye de la forma ,
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| ≥ m, x puode ser rescrito de la forma wyç, |y| ≤ m, i ∀ i, i ≥ 0  &esin; L

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

 Refréncias 

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

Catadorie:Lenguaiges formales
Catadorie:Teorie de la cumputaçon