Lenguaje regular

En teoría de la computación y lingüística computacional, un lenguaje regular es un lenguaje formal que puede ser definido por una expresión regular, generado por una gramática regular, y reconocido por un autómata finito.

Los lenguajes regulares son los lenguajes formales más sencillos (tipo 3) en la Jerarquía de Chomsky.

Definición formal

Un lenguaje regular sobre un alfabeto $\Sigma$ dado se define recursivamente como:

• El lenguaje vacío $\varnothing$ es un lenguaje regular
• El lenguaje cadena vacía {ε} es un lenguaje regular
• Para todo símbolo a ∈ $\Sigma$ {a} es un lenguaje regular
• Si A y B son lenguajes regulares entonces A ∪ B (unión), A•B (concatenación) y A^* (clausura o estrella de Kleene) son lenguajes regulares
• Si A es un lenguaje regular entonces (A) es el mismo lenguaje regular
• No existen más lenguajes regulares sobre $\Sigma$

Todo lenguaje formal finito constituye un lenguaje regular. Otros ejemplos típicos son todas las cadenas sobre el alfabeto {a, b} que contienen un número par de aes o el lenguaje que consiste en varias aes seguidas de varias bes.

Si un lenguaje no es regular requiere una máquina con al menos una complejidad de Ω(log log n) (donde n es el tamaño de la entrada). En la práctica la mayoría de los problemas no regulares son resueltos con una complejidad logarítmica.

Un lenguaje formal infinito puede ser regular o no regular. El lenguaje L = {aⁿ, n > 0} es regular porque puede ser representado, por ejemplo, mediante la expresión regular a⁺. El lenguaje L= {aⁿ bⁿ, n > 0} es un lenguaje no regular dado que no es reconocido por ninguna de las formas de representación anteriormente enumeradas.

Propiedades de cierre

Los lenguajes regulares son cerrados con las siguientes operaciones, de modo que si L y P son lenguajes regulares los siguientes lenguajes también serán regulares:

• El complemento ${\bar {''L''}}$ de L
• La clausura o estrella de Kleene L^* de L
• El homomorfismo φ(L) de L
• La concatenación L'P de L y P
• La unión L ∪ P de L y P
• La intersección L ∩ P de L y P
• La diferencia L \ P de L y P
• El reverso L^R de L

Problemas de decisión

Dados dos autómatas finitos deterministas A y B, como consecuencia de las propiedades de clausura, los siguientes problemas son también decidibles para cualquier autómata finito determinista A y B, con L_A y L_B los lenguajes que son aceptados por los autómatas respectivamente:

• Pertenencia: ¿Pertenece L_A a L_B?
• Intersección vacía: ¿L_A ∩ L_B vacío?
• Lenguaje vacío. ¿Es L_A vacío?
• Pertenencia. Dado w que pertenece a Σ*, ¿esta w en L_A?

Decidir cuándo un lenguaje es regular

Para situar los lenguajes regulares en la jerarquía de Chomsky hay que notar que todo lenguaje regular es también un lenguaje libre de contexto, aunque la afirmación contraria no es cierta, por ejemplo: el lenguaje que contiene el mismo número de 'a's y de 'b's es libre de contexto pero no regular. Para probar que un lenguaje de este tipo no es regular se usa el teorema de Myhill-Nerode, o el lema de bombeo por ejemplo.

Hay dos aproximaciones puramente algebraicas para definir lenguajes regulares. Si $\Sigma$ es un alfabeto finito y $\Sigma$^* es un monoide libre consistente en todas las cadenas sobre $\Sigma$, f: $\Sigma$^* → M es un monoide simétrico donde M es un monoide finito y S es un subconjunto de M entonces el conjunto f^-1(S) es regular. Todo lenguaje regular se presenta de esta manera.

Si L es un subconjunto de Σ*, se define la relación equivalente ~ en Σ* de la siguiente manera: u ~ v significa

uw ∈ L si y solo si vw ∈ L para todo w ∈ Σ*

El lenguaje L es regular si y solo si el número de clases de equivalencia de ~ es finito; si este es el caso, este número es igual al número de estados del autómata determinista mínimo que reconocerá L.

Lenguajes finitos

Un subconjunto especial de los lenguajes regulares es el de los lenguajes finitos, aquellos que solo contienen un número finito de palabras. Estos son lenguajes obviamente regulares y uno podría crear expresiones regulares que serían la unión de todas las palabras del lenguaje que definirían dicho lenguaje.

Enlaces externos

• Wikimedia Commons alberga una categoría multimedia sobre Lenguaje regular.
• Chalchalero! Archivado el 18 de enero de 2007 en Wayback Machine. Software visual gratuito para trabajar con lenguajes regulares, expresiones regulares, gramáticas regulares y autómatas finitos. Proyecto SEPa! (Universidad Católica de Santiago del Estero)

• Datos: Q752532
• Multimedia: Regular language / Q752532