Lenguaje regular

En la informática teórica y la teoría del lenguaje formal , un lenguaje regular (también llamado lenguaje racional ) ^{[ 1 ] [ 2 ]} es un lenguaje formal que puede definirse mediante una expresión regular , en el sentido estricto de la informática teórica (a diferencia de muchos motores de expresiones regulares modernos, que se han aumentado con características que permiten el reconocimiento de lenguajes no regulares).

Alternativamente, un lenguaje regular puede definirse como un lenguaje reconocido por un autómata finito . La equivalencia entre expresiones regulares y autómatas finitos se conoce como el teorema de Kleene ^{[ 3 ]} (en honor al matemático estadounidense Stephen Cole Kleene ). En la jerarquía de Chomsky , los lenguajes regulares son los lenguajes generados por gramáticas de tipo 3 .

La colección de lenguajes regulares sobre un alfabeto Σ se define recursivamente de la siguiente manera:

• El lenguaje vacío ∅ es un lenguaje regular.
• Para cada a ∈ Σ ( a pertenece a Σ), el lenguaje unitario { a } es un lenguaje regular.
• Si A es un lenguaje regular, A * ( estrella de Kleene ) es un lenguaje regular. Por lo tanto, el lenguaje de cadena vacía {ε} también es regular.
• Si A y B son lenguajes regulares, entonces A ∪ B (unión) y A • B (concatenación) son lenguajes regulares.
• Ningún otro idioma por encima de Σ es regular.

Consulte Expresiones regulares §  Teoría del lenguaje formal para la sintaxis y la semántica de las expresiones regulares.

Todos los lenguajes finitos son regulares; en particular, el lenguaje de cadenas vacías {ε} = ∅* es regular. Otros ejemplos típicos incluyen el lenguaje que consta de todas las cadenas sobre el alfabeto { a , b } que contienen un número par de a , o el lenguaje que consta de todas las cadenas de la forma: varias a seguidas de varias b .

Un ejemplo sencillo de un lenguaje no regular es el conjunto de cadenas { a ⁿ b ⁿ | n ≥ 0} . ^{[ 4 ]} Intuitivamente, no puede ser reconocido con un autómata finito, ya que un autómata finito tiene memoria finita y no puede recordar el número exacto de a. A continuación se presentan técnicas para demostrar este hecho rigurosamente .

Un lenguaje regular satisface las siguientes propiedades equivalentes:

1. es el lenguaje de una expresión regular (según la definición anterior)
2. es el lenguaje aceptado por un autómata finito no determinista (AFN) ^{[ nota 1 ] [ nota 2 ]}
3. es el lenguaje aceptado por un autómata finito determinista (AFD) ^{[ nota 3 ] [ nota 4 ]}
4. puede ser generado por una gramática regular ^{[ nota 5 ] [ nota 6 ]}
5. es el lenguaje aceptado por un autómata finito alternante
6. Es el lenguaje aceptado por un autómata finito bidireccional.
7. Se puede generar mediante una gramática de prefijos.
8. Puede ser aceptado por una máquina de Turing de solo lectura.
9. se puede definir en lógica monádica de segundo orden ( teorema de Büchi–Elgot–Trakhtenbrot ) ^{[ 5 ]}
10. es reconocido por algún monoide sintáctico finito M , lo que significa que es la preimagen { w ∈ Σ ^* | f ( w ) ∈ S } de un subconjunto S de un monoide finito M bajo un homomorfismo de monoide f  : Σ ^* → M del monoide libre en su alfabeto ^{[ nota 7 ]}
11. El número de clases de equivalencia de su congruencia sintáctica es finito. ^{[ nota 8 ] [ nota 9 ]} (Este número es igual al número de estados del autómata finito determinista mínimo que acepta L. )

Las propiedades 10 y 11 son enfoques puramente algebraicos para definir lenguajes regulares; se puede formular un conjunto similar de enunciados para un monoide M ⊆ Σ ^* . En este caso, la equivalencia sobre M conduce al concepto de lenguaje reconocible.

Algunos autores utilizan una de las propiedades anteriores, distinta de "1.", como definición alternativa de lenguajes regulares.

Algunas de las equivalencias anteriores, en particular las de los cuatro primeros formalismos, se denominan teorema de Kleene en los libros de texto. La denominación precisa de cuál (o subconjunto) se utiliza varía entre autores. Un libro de texto denomina a la equivalencia entre expresiones regulares y autómatas finitos no deterministas (AFND) ("1." y "2." arriba) "teorema de Kleene". ^{[ 6 ]} Otro libro de texto denomina a la equivalencia entre expresiones regulares y autómatas finitos deterministas (AFD) ("1." y "3." arriba) "teorema de Kleene". ^{[ 7 ]} Otros dos libros de texto primero demuestran la equivalencia expresiva entre AFND y AFD ("2." y "3.") y luego enuncian el "teorema de Kleene" como la equivalencia entre expresiones regulares y autómatas finitos (estos últimos, según se dice, describen "lenguajes reconocibles"). ^{[ 2 ] [ 8 ]} Un texto orientado lingüísticamente primero equipara las gramáticas regulares ("4." arriba) con los AFD y los AFN, llama a los lenguajes generados por (cualquiera de) estos "regulares", luego introduce expresiones regulares que denomina para describir "lenguajes racionales", y finalmente enuncia el "teorema de Kleene" como la coincidencia de lenguajes regulares y racionales. ^{[ 9 ]} Otros autores simplemente definen "expresión racional" y "expresiones regulares" como sinónimos y hacen lo mismo con "lenguajes racionales" y "lenguajes regulares". ^{[ 1 ] [ 2 ]}

Aparentemente, el término «regular» tiene su origen en un informe técnico de 1951 donde Kleene introdujo los eventos regulares y acogió explícitamente «cualquier sugerencia sobre un término más descriptivo». ^{[ 10 ]} Noam Chomsky , en su artículo fundamental de 1959, utilizó el término «regular» con un significado diferente al principio (refiriéndose a lo que hoy se denomina forma normal de Chomsky ), ^{[ 11 ]} pero observó que sus lenguajes de estados finitos eran equivalentes a los eventos regulares de Kleene . ^{[ 12 ]}

Los lenguajes regulares son cerrados bajo diversas operaciones, es decir, si los lenguajes K y L son regulares, también lo es el resultado de las siguientes operaciones:

• las operaciones booleanas de ^la teoría de conjuntos : unión K ∪ L , intersección K ∩ L y complemento L , por lo tanto también complemento relativo K − L. ^{[ 13} ]
• las operaciones regulares: K ∪ L , concatenación ⁠${\displaystyle K\circ L}$⁠ , y la estrella de Kleene L ^* . ^{[ 14 ]}
• Las operaciones del trío son: homomorfismo de cadenas , homomorfismo inverso de cadenas e intersección con lenguajes regulares. En consecuencia, son cerradas bajo transducciones de estados finitos arbitrarias , como el cociente K / L con un lenguaje regular. Más aún, los lenguajes regulares son cerrados bajo cocientes con lenguajes arbitrarios : si L es regular, entonces ^L / K es regular para cualquier K. ^{[ 15} ]
• la inversa (o imagen especular) L ^R . ^{[ 16 ]} Dado un autómata finito no determinista para reconocer L , se puede obtener un autómata para L ^R invirtiendo todas las transiciones e intercambiando los estados inicial y final. Esto puede resultar en múltiples estados iniciales; se pueden usar transiciones ε para unirlos.

Dados dos autómatas finitos deterministas A y B , es decidible si aceptan el mismo lenguaje. ^{[ 17 ]} En consecuencia, utilizando las propiedades de cierre anteriores , los siguientes problemas también son decidibles para autómatas finitos deterministas A y B dados arbitrariamente , con lenguajes aceptados L _A y L _B , respectivamente:

• Contención: ¿es L _A ⊆ L _B  ? ^{[ nota 10 ]}
• Disyunción: ¿es L _A ∩ L _B = {}  ?
• Vacío: ¿es L _A = {}  ?
• Universalidad: ¿es L _A = Σ ^*  ?
• Pertenencia: dado a ∈ Σ ^* , ¿es a ∈ L _B  ?

Para expresiones regulares, el problema de universalidad es NP-completo incluso para un alfabeto unitario. ^{[ 18 ]} Para alfabetos más grandes, ese problema es PSPACE-completo . ^{[ 19 ]} Si las expresiones regulares se extienden para permitir también un operador de cuadratura , donde " A2 ^" denota lo mismo que " AA ", aún se pueden describir solo lenguajes regulares, pero el problema de universalidad tiene una cota inferior de espacio exponencial, ^{[ 20 ] [ 21 ] [ 22 ]} y de hecho es completo para espacio exponencial con respecto a la reducción en tiempo polinomial. ^{[ 23 ]}

Para un alfabeto finito fijo, la teoría del conjunto de todos los lenguajes —junto con las cadenas, la pertenencia de una cadena a un lenguaje y, para cada carácter, una función para añadir el carácter a una cadena (y ninguna otra operación)— es decidible, y su subestructura elemental mínima consiste precisamente en lenguajes regulares. Para un alfabeto binario, la teoría se denomina S2S . ^{[ 24 ]}

En la teoría de la complejidad computacional , la clase de complejidad de todos los lenguajes regulares a veces se denomina REGULAR o REG y es igual a DSPACE (O(1)), los problemas de decisión que se pueden resolver en espacio constante (el espacio utilizado es independiente del tamaño de la entrada). REGULAR ≠ AC ⁰ , ya que (trivialmente) contiene el problema de paridad de determinar si el número de bits 1 en la entrada es par o impar y este problema no está en AC ⁰ . ^{[ 25 ]} Por otro lado, REGULAR no contiene AC ⁰ , porque el lenguaje no regular de palíndromos , o el lenguaje no regular${\displaystyle \{0^{n}1^{n}:n\in \mathbb {N} \}}$Ambos pueden ser reconocidos en AC ⁰ . ^{[ 26 ]}

Si un lenguaje no es regular, requiere una máquina con al menos Ω (log log n ) espacio para reconocerlo (donde n es el tamaño de entrada). ^{[ 27 ]} En otras palabras, DSPACE( o (log log n )) es igual a la clase de lenguajes regulares. ^{[ 27 ]} En la práctica, la mayoría de los problemas no regulares se estudian en un entorno con al menos espacio logarítmico , ya que esta es la cantidad de espacio necesaria para almacenar un puntero en la cinta de entrada. ^{[ 28 ]}

Para ubicar los lenguajes regulares en la jerarquía de Chomsky , se observa que todo lenguaje regular es libre de contexto . Lo contrario no es cierto: por ejemplo, el lenguaje que consiste en todas las cadenas con el mismo número de a que de b es libre de contexto, pero no regular. Para demostrar que un lenguaje no es regular, se suele utilizar el teorema de Myhill-Nerode y el lema de bombeo . Otros enfoques incluyen el uso de las propiedades de cierre de los lenguajes regulares ^{[ 29 ]} o la cuantificación de la complejidad de Kolmogorov ^{[ 30 ]} .

Entre las subclases importantes de los lenguajes regulares se incluyen:

• Lenguajes finitos, aquellos que contienen solo un número finito de palabras. ^{[ 31 ]} Estos son lenguajes regulares, ya que se puede crear una expresión regular que es la unión de cada palabra del lenguaje.
• Lenguajes sin estrella , aquellos que pueden describirse mediante una expresión regular construida a partir del símbolo vacío, letras, concatenación y todos los operadores booleanos (véase álgebra de conjuntos ), incluyendo la complementación pero no la estrella de Kleene : esta clase incluye todos los lenguajes finitos. ^{[ 32 ]}

Dejar${\displaystyle s_{L}(n)}$denota el número de palabras de longitud${\displaystyle n}$en${\displaystyle L}$La función generadora ordinaria para L es la serie de potencias formal .

${\displaystyle S_{L}(z)=\sum _ {n\geq 0}s_{L}(n)z^{n}\ .}$

La función generadora de un lenguaje L es una función racional si L es regular. ^{[ 33 ]} Por lo tanto, para todo lenguaje regular${\displaystyle L}$la secuencia${\displaystyle s_{L}(n)_{n\geq 0}}$es recursiva constante ; es decir, existe una constante entera .${\displaystyle n_{0}}$constantes complejas​${\displaystyle \lambda _{1},\,\ldots ,\,\lambda _{k}}$y polinomios complejos${\displaystyle p_{1}(x),\,\ldots ,\,p_{k}(x)}$de tal manera que para cada${\displaystyle n\geq n_{0}}$el número${\displaystyle s_{L}(n)}$de palabras de longitud${\displaystyle n}$en${\displaystyle L}$es${\displaystyle s_{L}(n)=p_{1}(n)\lambda _{1}^{n}+\dotsb +p_{k}(n)\lambda _{k}^{n}}$. ^{[ 34 ] [ 35 ] [ 36 ] [ 37 ]}

Por lo tanto, la irregularidad de ciertos lenguajes${\displaystyle L'}$se puede probar contando las palabras de una longitud determinada en ${\displaystyle L'}$. Consideremos, por ejemplo, el lenguaje Dyck de cadenas de paréntesis balanceados. El número de palabras de longitud${\displaystyle 2n}$ en el idioma de Dyck es igual al número catalán${\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}}$, que no es de la forma${\displaystyle p(n)\lambda ^{n}}$, siendo testigo de la irregularidad del lenguaje de Dyck. Se debe tener cuidado ya que algunos de los autovalores${\displaystyle \lambda _{i}}$podría tener la misma magnitud. Por ejemplo, el número de palabras de longitud${\displaystyle n}$en el lenguaje de todas las palabras binarias pares no es de la forma${\displaystyle p(n)\lambda ^{n}}$, pero el número de palabras de longitud par o impar son de esta forma; los autovalores correspondientes son${\displaystyle 2,-2}$En general, para cada lenguaje regular existe una constante${\displaystyle d}$de tal manera que para todos${\displaystyle a}$, el número de palabras de longitud${\displaystyle dm+a}$es asintóticamente${\displaystyle C_{a}m^{p_{a}}\lambda _{a}^{m}}$. ^{[ 38 ]}

La función zeta de un lenguaje L es ^{[ 33 ]}

${\displaystyle \zeta _{L}(z)=\exp \left({\sum _{n\geq 0}s_{L}(n){\frac {z^{n}}{n}}}\right).}$

La función zeta de un lenguaje regular no es racional en general, pero la de un lenguaje cíclico arbitrario sí lo es. ^{[ 39 ] [ 40 ]}

La noción de lenguaje regular se ha generalizado a palabras infinitas (véase autómatas ω ) y a árboles (véase autómata de árbol ).

El conjunto racional generaliza la noción (de lenguaje regular/racional) a monoides que no son necesariamente libres . Del mismo modo, la noción de un lenguaje reconocible (por un autómata finito) tiene su homólogo como conjunto reconocible sobre un monoide que no es necesariamente libre. Howard Straubing señala en relación con estos hechos que “El término «lenguaje regular» es un tanto desafortunado. Los artículos influenciados por la monografía de Eilenberg ^{[ 41 ]} suelen usar el término «lenguaje reconocible», que se refiere al comportamiento de los autómatas, o «lenguaje racional», que se refiere a importantes analogías entre expresiones regulares y series de potencias racionales . (De hecho, Eilenberg define subconjuntos racionales y reconocibles de monoides arbitrarios; las dos nociones no coinciden, en general). Esta terminología, aunque mejor justificada, nunca llegó a popularizarse, y «lenguaje regular» se usa casi universalmente”. ^{[ 42 ]}

Las series racionales son otra generalización, esta vez en el contexto de una serie de potencias formal sobre un semianillo . Este enfoque da lugar a expresiones racionales ponderadas y autómatas ponderados . En este contexto algebraico, los lenguajes regulares (que corresponden a expresiones racionales ponderadas booleanas ) se denominan habitualmente lenguajes racionales . ^{[ 43 ] [ 44 ]} También en este contexto, el teorema de Kleene encuentra una generalización denominada teorema de Kleene-Schützenberger .

• Kleene, SC : Representación de eventos en redes nerviosas y autómatas finitos. En: Shannon, CE, McCarthy, J. (eds.) Automata Studies, pp.  3–41. Princeton University Press, Princeton (1956); es una versión ligeramente modificada de su informe de 1951 para la RAND Corporation del mismo título, RM704 .
• Sakarovitch, J (1987). "El teorema de Kleene revisitado". Tendencias, técnicas y problemas en informática teórica . Notas de clase en informática. Vol.  1987. pp. 39–50 . doi : 10.1007/3540185356_29 . ISBN  978-3-540-18535-2.

• Zoológico de complejidad : Clase REG