Lenguaje regular - Regular language

En la informática teórica y la teoría del lenguaje formal , un lenguaje regular (también llamado lenguaje racional ) 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 modernos de expresiones regulares, que se complementan con funciones que permiten el reconocimiento de idiomas no regulares).

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

Definicion formal

La colección de idiomas regulares sobre un alfabeto Σ se define de forma recursiva de la siguiente manera:

• El idioma vacío Ø es un idioma regular.
• Para cada a ∈ Σ ( a pertenece a Σ), el lenguaje singleton { a } es un lenguaje regular.
• Si A es un idioma regular, A * ( estrella de Kleene ) es un idioma regular. Debido a esto, el lenguaje de cadenas vacías {ε} también es regular.
• Si A y B son idiomas regulares, entonces A ∪ B (unión) y A • B (concatenación) son idiomas regulares.
• Ningún otro idioma por encima de Σ es regular.

Consulte expresión regular para conocer la sintaxis y la semántica de las expresiones regulares.

Ejemplos de

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 s, o el lenguaje que consta de todas las cadenas de la forma: varias a s seguidas de varias b s.

Un ejemplo simple de un lenguaje que no es regular es el conjunto de cadenas { a ⁿ b ⁿ | n ≥ 0}. Intuitivamente, no se puede reconocer con un autómata finito, ya que un autómata finito tiene memoria finita y no puede recordar el número exacto de a. Las técnicas para probar este hecho rigurosamente se dan a continuación .

Formalismos equivalentes

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 (NFA)
3. es el lenguaje aceptado por un autómata finito determinista (DFA)
4. puede ser generado por una gramática regular
5. es el lenguaje aceptado por un autómata finito alterno
6. es el lenguaje aceptado por un autómata finito bidireccional
7. puede ser generado por un prefijo gramatical
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 )
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
11. el número de clases de equivalencia de su congruencia sintáctica es finito. (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 declaraciones para un monoide M ⊆ Σ ^* . En este caso, la equivalencia sobre M conduce al concepto de un lenguaje reconocible.

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

Algunas de las equivalencias anteriores, en particular las que se encuentran entre los primeros cuatro formalismos, se denominan teorema de Kleene en los libros de texto. Precisamente cuál (o qué subconjunto) se llama así varía entre los autores. Un libro de texto llama a la equivalencia de expresiones regulares y NFA ("1" y "2" arriba) "teorema de Kleene". Otro libro de texto llama a la equivalencia de expresiones regulares y DFA ("1." y "3." arriba) "teorema de Kleene". Otros dos libros de texto primero prueban la equivalencia expresiva de NFA y DFA ("2" y "3") y luego establecen el "teorema de Kleene" como la equivalencia entre expresiones regulares y autómatas finitos (se dice que este último describe "lenguajes reconocibles") . Un texto de orientación lingüística primero equipara las gramáticas regulares ("4" arriba) con DFA y NFA, llama a los lenguajes generados por (cualquiera de) estos "regulares", después de lo cual introduce expresiones regulares que denomina para describir "lenguajes racionales". y finalmente establece el "teorema de Kleene" como la coincidencia de lenguajes regulares y racionales. Otros autores simplemente definen "expresión racional" y "expresiones regulares" como sinónimos y hacen lo mismo con "lenguajes racionales" y "lenguajes regulares".

Aparentemente, el término "regular" se origina en un informe técnico de 1951 donde Kleene introdujo "eventos regulares" y expresamente agradeció "cualquier sugerencia en cuanto a un término más descriptivo" . Noam Chomsky , en su artículo seminal de 1959, usó el término "regular" con un significado diferente al principio (refiriéndose a lo que hoy se llama " forma normal de Chomsky " ), pero notó que sus "lenguajes estatales finitos" eran equivalentes a los "lenguajes regulares de Kleene ". eventos " .

Propiedades de cierre

Los lenguajes regulares se cierran bajo varias 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 teoría de conjuntos : unión K ∪ L , intersección K ∩ L , y complemento L , por lo tanto, también complemento relativa K - L .
• las operaciones regulares: K ∪ L , concatenación y estrella de Kleene L ^* .${\ Displaystyle K \ circ L}$
• las operaciones del trío : homomorfismo de cuerdas , homomorfismo de cuerdas inverso e intersección con lenguajes regulares. Como consecuencia, están cerrados bajo transducciones arbitrarias de estado finito , como el cociente K / L con un lenguaje regular. Aún más, los lenguajes regulares son cerrados bajo cocientes con arbitrarias idiomas: Si L es regular, entonces L / K es normal para cualquier K .
• a la inversa (o imagen de espejo) L ^R . 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 estados de inicio y finalización. Esto puede resultar en múltiples estados iniciales; Se pueden usar transiciones ε para unirlas.

Propiedades de decidabilidad

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

• Contención: ¿ L _A ⊆ L _B  ?
• Disjunción: ¿es L _A ∩ L _B = {}?
• Vacío: ¿ L _A = {}?
• Universalidad: ¿ L _A = Σ ^*  ?
• Membresía: dado un ∈ Σ ^* , ¿es un ∈ L _B  ?

Para las expresiones regulares, el problema de universalidad ya es NP-completo para un alfabeto singleton. Para alfabetos más grandes, ese problema es PSPACE completo . Si las expresiones regulares se extienden para permitir también un operador de cuadratura , con " A ² " denotando lo mismo que " AA ", todavía solo se pueden describir los lenguajes regulares, pero el problema de universalidad tiene un límite inferior de espacio exponencial, y de hecho está completo para espacio exponencial con respecto a la reducción del tiempo polinomial.

Resultados de complejidad

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 un espacio constante (el espacio utilizado es independiente del tamaño de entrada ). REGULAR ≠ AC ⁰ , ya que (trivialmente) contiene el problema de paridad de determinar si el número de 1 bits en la entrada es par o impar y este problema no está en AC ⁰ . Por otro lado, REGULAR no contiene AC ⁰ , porque el lenguaje no regular de los palíndromos , o el lenguaje no regular, pueden reconocerse ambos en AC ⁰ . ${\ Displaystyle \ {0 ^ {n} 1 ^ {n}: n \ in \ mathbb {N} \}}$

Si un idioma no es regular, se requiere una máquina con al menos Ω (log log n ) de espacio para reconocerlo (donde n es el tamaño de entrada). En otras palabras, DSPACE ( o (log log n )) es igual a la clase de lenguajes regulares. En la práctica, la mayoría de los problemas no regulares se resuelven mediante máquinas que ocupan al menos un espacio logarítmico .

Ubicación en la jerarquía de Chomsky

Lenguaje regular en clases de jerarquía de Chomsky.

Para ubicar los idiomas regulares en la jerarquía de Chomsky , uno se da cuenta de que todos los idiomas regulares están libres de contexto . Lo contrario no es cierto: por ejemplo, el lenguaje que consta de todas las cadenas que tienen el mismo número de a que de b no tiene contexto, pero no es regular. Para demostrar que un idioma no es regular, a menudo se usa el teorema de Myhill-Nerode y el lema de bombeo . Otros enfoques incluyen el uso de las propiedades de cierre de los lenguajes regulares o la cuantificación de la complejidad de Kolmogorov .

Las subclases importantes de lenguajes regulares incluyen

• Lenguajes finitos, aquellos que contienen solo un número finito de palabras. Estos son lenguajes regulares, ya que se puede crear una expresión regular que sea la unión de cada palabra en el idioma.
• Lenguajes sin estrellas , 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 (ver álgebra de conjuntos ) incluida la complementación pero no la estrella de Kleene : esta clase incluye todos los lenguajes finitos.

La cantidad de palabras en un idioma regular.

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

${\ 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. Por tanto, para cada idioma regular, la secuencia es constante-recursiva ; es decir, existe una constante entera , constantes complejas y polinomios complejos tales que para cada número de palabras de longitud en es . ${\ Displaystyle L}$${\ Displaystyle s_ {L} (n) _ {n \ geq 0}}$${\ Displaystyle n_ {0}}$${\ Displaystyle \ lambda _ {1}, \, \ ldots, \, \ lambda _ {k}}$${\ Displaystyle p_ {1} (x), \, \ ldots, \, p_ {k} (x)}$${\ Displaystyle n \ geq n_ {0}}$${\ Displaystyle s_ {L} (n)}$${\ Displaystyle n}$${\ Displaystyle L}$${\ Displaystyle s_ {L} (n) = p_ {1} (n) \ lambda _ {1} ^ {n} + \ dotsb + p_ {k} (n) \ lambda _ {k} ^ {n}}$

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

La función zeta de una lengua L es

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

La función zeta de un lenguaje regular no es en general racional, pero la de un lenguaje cíclico arbitrario sí lo es.

Generalizaciones

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

El conjunto racional generaliza la noción (de lenguaje regular / racional) a monoides que no son necesariamente libres . Asimismo, la noción de un lenguaje reconocible (por un autómata finito) tiene homónimo 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 común "es un poco desafortunado. Los artículos influenciados por la monografía de Eilenberg a menudo usan el término "lenguaje reconocible", que se refiere al comportamiento de los autómatas, o "lenguaje racional", que se refiere a analogías importantes entre expresiones regulares y series de potencias racionales. (De hecho, Eilenberg define subconjuntos racionales y reconocibles de monoides arbitrarios; las dos nociones, en general, no coinciden). Esta terminología, aunque está mejor motivada, nunca se puso de moda y el "lenguaje regular" se usa casi universalmente ".

La serie racional es otra generalización, esta vez en el contexto de una serie de poder formal sobre un semirrígido . Este enfoque da lugar a expresiones racionales ponderadas y autómatas ponderados . En este contexto algebraico, los lenguajes regulares (correspondientes a las expresiones racionales ponderadas de Boole ) se denominan habitualmente lenguajes racionales . También en este contexto, el teorema de Kleene encuentra una generalización llamada teorema de Kleene-Schützenberger .

Aprendiendo de los ejemplos

Notas

Referencias

Otras lecturas

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

enlaces externos

• Medios relacionados con el lenguaje regular en Wikimedia Commons
• Complejidad Zoo : Clase REG