Lenguaje regular

Lenguaje formal que puede expresarse mediante una expresión regular

En informática teórica y 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 amplían 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 de 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 .

Definición formal

La colección de idiomas regulares sobre un alfabeto Σ se define recursivamente 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 lenguaje regular, A *( estrella de Kleene ) es un lenguaje regular. Por ello, la cadena vacía language {ε} 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 mayor que Σ es regular.

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

Ejemplos

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

Un ejemplo sencillo de un lenguaje que no es regular es el conjunto de cadenas { a ⁿ b ⁿ | n ≥ 0}. ^[4] 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. A continuación se ofrecen técnicas para demostrar este hecho rigurosamente.

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) ^{[nota 1] [nota 2]}
3. es el lenguaje aceptado por un autómata finito determinista (DFA) ^{[nota 3] [nota 4]}
4. Puede generarse mediante una gramática regular ^{[nota 5] [nota 6]}
5. Es el lenguaje aceptado por un autómata finito alterno.
6. Es el lenguaje aceptado por un autómata finito bidireccional.
7. Puede generarse mediante una gramática de prefijo.
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 afirmaciones 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 definición alternativa de los lenguajes regulares.

Algunas de las equivalencias anteriores, en particular las que se dan entre los primeros cuatro formalismos, se denominan teorema de Kleene en los libros de texto. El nombre exacto de una de ellas (o de un subconjunto de ellas) varía entre los distintos autores. Un libro de texto denomina a la equivalencia de expresiones regulares y autómatas finitos ("1." y "2." arriba) "teorema de Kleene". ^[6] Otro libro de texto denomina a la equivalencia de expresiones regulares y autómatas finitos ("1." y "3." arriba) "teorema de Kleene". ^[7] Otros dos libros de texto demuestran primero la equivalencia expresiva de autómatas finitos y autómatas finitos ("2." y "3.") y luego enuncian el "teorema de Kleene" como la equivalencia entre expresiones regulares y autómatas finitos (se dice que este último describe "lenguajes reconocibles"). ^{[2] [8]} Un texto orientado lingüísticamente primero equipara las gramáticas regulares ("4." arriba) con los DFA y los 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 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]}

Al parecer, el término "regular" tiene su origen en un informe técnico de 1951 en el que Kleene introdujo los "eventos regulares" y acogió con agrado "cualquier sugerencia sobre un término más descriptivo" . ^[10] Noam Chomsky , en su artículo seminal 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 se dio cuenta de que sus "lenguajes de estados finitos" eran equivalentes a los "eventos regulares" de Kleene . ^[12]

Propiedades del cierre

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 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 estrella de Kleene L ^* . ^[14]
• las operaciones de trío : homomorfismo de cuerdas , homomorfismo de cuerdas inverso e intersección con lenguajes regulares. En consecuencia, están cerradas bajo transducciones de estados finitos arbitrarios , como el cociente K / L con un lenguaje regular. Más aún, los lenguajes regulares están cerrados bajo cocientes con lenguajes arbitrarios : si L es regular, entonces L / K es regular para cualquier K. ^[15]
• el inverso (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 dar como resultado múltiples estados iniciales; se pueden usar ε-transiciones para unirlos.

Propiedades de decidibilidad

Dados dos autómatas finitos deterministas A y B , es decidible si aceptan el mismo lenguaje. ^[17] Como consecuencia, utilizando las propiedades de cierre anteriores, los siguientes problemas también son decidibles para autómatas finitos deterministas dados arbitrariamente A y B , 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 = Σ ^*  ?
• Membresía: dado un ∈ Σ ^* , es a ∈ L _B  ?

Para las expresiones regulares, el problema de universalidad es NP-completo ya para un alfabeto singleton. ^[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 , con " A ² " denotando lo mismo que " AA ", todavía se pueden describir solo lenguajes regulares, pero el problema de universalidad tiene un límite inferior de espacio exponencial, ^{[20] [21] [22]} y de hecho es completo para el espacio exponencial con respecto a la reducción de tiempo polinomial. ^[23]

Para un alfabeto finito fijo, la teoría del conjunto de todos los idiomas —junto con las cadenas, la pertenencia de una cadena a un idioma 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 idiomas regulares. Para un alfabeto binario, la teoría se llama S2S . ^[24]

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 el espacio constante (el espacio utilizado es independiente del tamaño de entrada). REGULAR ≠ AC 0 , 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 pueden reconocerse en AC ⁰ . ^[26] ${\displaystyle \{0^{n}1^{n}:n\in \mathbb {N} \}}$

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. 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

El lenguaje regular en las clases de la jerarquía de Chomsky

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

Las subclases importantes de los lenguajes regulares incluyen

• Lenguajes finitos, aquellos que contienen sólo un número finito de palabras. ^[30] Éstos son lenguajes regulares, ya que se puede crear una expresión regular que sea 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 ), incluida la complementación pero no la estrella de Kleene : esta clase incluye todos los lenguajes finitos. ^[31]

El número de palabras en un idioma regular.

Sea el número de palabras de longitud en . La función generadora ordinaria para L es la serie de potencias 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. ^[32] Por lo tanto, para cada lenguaje regular la secuencia es recursiva-constante ; es decir, existen una constante entera , constantes complejas y polinomios complejos tales que para cada el número de palabras de longitud en es . ^{[33] [34] [35] [36]} ${\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}}$

Así, la no regularidad de ciertas lenguas se puede demostrar contando las palabras de una longitud dada en . Consideremos, por ejemplo, el lenguaje Dyck de cadenas de paréntesis balanceados. El número de palabras de longitud en el lenguaje Dyck es igual al número catalán , que no tiene la forma , lo que atestigua la no regularidad del lenguaje 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 lenguaje 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 lenguaje regular existe una constante tal que para todos , el número de palabras de longitud es asintóticamente . ^[37] ${\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 un lenguaje L es ^[32]

${\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 en general racional, pero la de un lenguaje cíclico arbitrario sí lo es. ^{[38] [39]}

Generalizaciones

La noción de lenguaje regular se ha generalizado a infinitas palabras (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 . De la misma manera, la noción de un lenguaje reconocible (por un autómata finito) tiene como homónimo un 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 poco desafortunado. Los artículos influenciados por la monografía de Eilenberg ^[40] 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 mejor motivada, nunca tuvo éxito, y "lenguaje regular" se usa casi universalmente”. ^[41]

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 (correspondientes a expresiones racionales ponderadas booleanas ) suelen denominarse lenguajes racionales . ^{[42] [43]} También en este contexto, el teorema de Kleene encuentra una generalización llamada teorema de Kleene-Schützenberger.

Aprendiendo de los ejemplos

Notas

1. 1. ⇒ 2. por el algoritmo de construcción de Thompson
2. 2. ⇒ 1. por el algoritmo de Kleene o usando el lema de Arden
3. 2. ⇒ 3. por la construcción del conjunto potencia
4. 3. ⇒ 2. ya que la primera definición es más fuerte que la segunda
5. 2. ⇒ 4. véase Hopcroft, Ullman (1979), Teorema 9.2, p.219
6. 4. ⇒ 2. véase Hopcroft, Ullman (1979), Teorema 9.1, p.218
7. 3. ⇔ 10. por el teorema de Myhill-Nerode
8. u ~ v se define como: uw ∈ L si y solo si vw ∈ L para todo w ∈Σ ^*
9. 3. ⇔ 11. Véase la prueba en el artículo sobre el monoide sintáctico y la pág. 160 en Holcombe, WML (1982). Teoría de autómatas algebraicos . Cambridge Studies in Advanced Mathematics. Vol. 1. Cambridge University Press . ISBN. 0-521-60492-3.Zbl 0489.68046  .
10. Verifique si L _A ∩ L _B = L _A . Decidir que esta propiedad es NP-hard en general; consulte Archivo:RegSubsetNP.pdf para ver una ilustración de la idea de prueba.

Referencias

• Berstel, Jean ; Reutenauer, Christophe (2011). Series racionales no conmutativas con aplicaciones . Enciclopedia de matemáticas y sus aplicaciones. Vol. 137. Cambridge: Cambridge University Press . ISBN 978-0-521-19022-0.Zbl 1250.68007  .
• Eilenberg, Samuel (1974). Autómatas, lenguajes y máquinas. Volumen A. Matemáticas puras y aplicadas. Vol. 58. Nueva York: Academic Press. Zbl  0317.94045.
• Salomaa, Arto (1981). Joyas de la teoría del lenguaje formal . Pitman Publishing. ISBN 0-273-08522-0.Zbl 0487.68064  .
• Sipser, Michael (1997). Introducción a la teoría de la computación . PWS Publishing. ISBN 0-534-94728-X.Zbl1169.68300  .​Capítulo 1: Lenguajes regulares, págs. 31–90. Subsección "Problemas decidibles relacionados con los lenguajes regulares" de la sección 4.1: Lenguajes decidibles, págs. 152–155.
• Philippe Flajolet y Robert Sedgewick, Combinatoria analítica : Combinatoria simbólica. Libro en línea, 2002.
• John E. Hopcroft; Jeffrey D. Ullman (1979). Introducción a la teoría de autómatas, lenguajes y computación . Addison-Wesley. ISBN 0-201-02988-X.
• Alfred V. Aho y John E. Hopcroft y Jeffrey D. Ullman (1974). El diseño y análisis de algoritmos informáticos . Addison-Wesley. ISBN 9780201000290.

1. Ruslan Mitkov (2003). Manual de Oxford de lingüística computacional. Oxford University Press. pág. 754. ISBN 978-0-19-927634-9.
2. Mark V. Lawson (2003). Autómatas finitos. CRC Press. págs. 98-103. ISBN 978-1-58488-255-8.
3. Sheng Yu (1997). "Lenguajes regulares". En Grzegorz Rozenberg; Arto Salomaa (eds.). Manual de lenguajes formales: Volumen 1. Palabra, lenguaje, gramática . Springer. pág. 41. ISBN 978-3-540-60420-4.
4. Eilenberg (1974), p. 16 (Ejemplo II, 2.8) y p. 25 (Ejemplo II, 5.2).
5. M. Weyer: Capítulo 12 - Decidibilidad de S1S y S2S, p. 219, Teorema 12.26. En: Erich Grädel, Wolfgang Thomas, Thomas Wilke (Eds.): Autómatas, lógicas y juegos infinitos: una guía para la investigación actual. Apuntes de clase en Ciencias de la Computación 2500, Springer 2002.
6. Robert Sedgewick; Kevin Daniel Wayne (2011). Algoritmos. Addison-Wesley Professional. pág. 794. ISBN 978-0-321-57351-3.
7. Jean-Paul Allouche; Jeffrey Shallit (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones. Cambridge University Press. pág. 129. ISBN 978-0-521-82332-6.
8. Kenneth Rosen (2011). Matemática discreta y sus aplicaciones, 7.ª edición. McGraw-Hill Science, págs. 873-880.
9. Horst Bunke; Alberto Sanfeliu (enero de 1990). Reconocimiento de patrones sintácticos y estructurales: teoría y aplicaciones. World Scientific. pág. 248. ISBN 978-9971-5-0566-0.
10. Stephen Cole Kleene (diciembre de 1951). Representación de eventos en redes nerviosas y autómatas finitos (PDF) (Memorando de investigación). Fuerza Aérea de EE. UU./Corporación RAND.Aquí: p.46
11. Noam Chomsky (1959). "Sobre ciertas propiedades formales de las gramáticas" (PDF) . Información y control . 2 (2): 137–167. doi : 10.1016/S0019-9958(59)90362-6 .Aquí: Definición 8, p.149
12. Chomsky 1959, nota al pie 10, p.150
13. Salomaa (1981) pág. 28
14. Salomaa (1981) pág. 27
15. Fellows, Michael R. ; Langston, Michael A. (1991). "Problemas de constructividad en algoritmos de grafos". En Myers, J. Paul Jr.; O'Donnell, Michael J. (eds.). Constructivity in Computer Science, Simposio de verano, San Antonio, Texas, EE. UU., 19-22 de junio, Actas . Apuntes de clase en informática. Vol. 613. Springer. págs. 150–158. doi :10.1007/BFB0021088.
16. Hopcroft, Ullman (1979), Capítulo 3, Ejercicio 3.4g, pág. 72
17. Hopcroft, Ullman (1979), Teorema 3.8, p.64; véase también Teorema 3.10, p.67
18. Aho, Hopcroft, Ullman (1974), Ejercicio 10.14, p.401
19. Aho, Hopcroft, Ullman (1974), Teorema 10.14, pág. 399
20. Hopcroft, Ullman (1979), Teorema 13.15, p.351
21. AR Meyer y LJ Stockmeyer (octubre de 1972). El problema de equivalencia para expresiones regulares con elevación al cuadrado requiere espacio exponencial (PDF) . 13.° Simposio anual IEEE sobre conmutación y teoría de autómatas. págs. 125-129.
22. LJ Stockmeyer; AR Meyer (1973). "Problemas verbales que requieren tiempo exponencial". Proc. 5th ann. symp. on Theory of computing (STOC) (PDF) . ACM. págs. 1–9.
23. Hopcroft, Ullman (1979), Corolario p.353
24. Weyer, Mark (2002). "Decidibilidad de S1S y S2S". Autómatas, lógicas y juegos infinitos . Apuntes de clase en informática. Vol. 2500. Springer. págs. 207–230. doi :10.1007/3-540-36387-4_12. ISBN. 978-3-540-00388-5.
25. Furst, Merrick; Saxe, James B .; Sipser, Michael (1984). "Paridad, circuitos y la jerarquía de tiempo polinomial". Teoría de sistemas matemáticos . 17 (1): 13–27. doi :10.1007/BF01744431. MR  0738749. S2CID  14677270.
26. Cook, Stephen; Nguyen, Phuong (2010). Fundamentos lógicos de la complejidad de las pruebas (1.ª ed. publ.). Ithaca, NY: Association for Symbolic Logic. p. 75. ISBN 978-0-521-51729-4.
27. J. Hartmanis, PL Lewis II y RE Stearns. Jerarquías de cálculos con memoria limitada. Actas del 6.º Simposio anual IEEE sobre teoría de circuitos de conmutación y diseño lógico , págs. 179-190. 1965.
28. "¿Cómo demostrar que un lenguaje no es regular?". cs.stackexchange.com . Consultado el 10 de abril de 2018 .
29. Hromkovič, Juraj (2004). Informática teórica: Introducción a los autómatas, la computabilidad, la complejidad, la algoritmia, la aleatorización, la comunicación y la criptografía. Springer. pp. 76–77. ISBN 3-540-14015-8.OCLC 53007120  .
30. Un lenguaje finito no debe confundirse con un lenguaje (generalmente infinito) generado por un autómata finito.
31. Volker Diekert; Paul Gastin (2008). "Lenguajes definibles de primer orden" (PDF) . En Jörg Flum; Erich Grädel; Thomas Wilke (eds.). Lógica y autómatas: historia y perspectivas . Amsterdam University Press. ISBN 978-90-5356-576-6.
32. Honkala, Juha (1989). "Una condición necesaria para la racionalidad de la función zeta de un lenguaje regular". Theor. Comput. Sci . 66 (3): 341–347. doi : 10.1016/0304-3975(89)90159-x . Zbl  0675.68034.
33. Flajolet y Sedgweick, sección V.3.1, ecuación (13).
34. "Número de palabras en el lenguaje regular $(00)^*$". cs.stackexchange.com . Consultado el 10 de abril de 2018 .
35. "Prueba del teorema para DFA arbitrarios".
36. "Número de palabras de una longitud determinada en un lenguaje regular". cs.stackexchange.com . Consultado el 10 de abril de 2018 .
37. Flajolet y Sedgewick (2002) Teorema V.3
38. Berstel, Jean; Reutenauer, Christophe (1990). "Funciones Zeta de lenguajes formales". Trans. Soy. Matemáticas. Soc . 321 (2): 533–546. CiteSeerX 10.1.1.309.3005 . doi :10.1090/s0002-9947-1990-0998123-x. Zbl  0797.68092. 
39. Berstel y Reutenauer (2011) p.222
40. Samuel Eilenberg. Autómatas, lenguajes y máquinas . Academic Press.en dos volúmenes "A" (1974, ISBN 9780080873749 ) y "B" (1976, ISBN 9780080873756 ), este último con dos capítulos de Bret Tilson.  
41. Straubing, Howard (1994). Autómatas finitos, lógica formal y complejidad de circuitos . Progreso en la ciencia informática teórica. Basilea: Birkhäuser. pág. 8. ISBN 3-7643-3719-2.Zbl 0816.68086  .
42. Berstel y Reutenauer (2011) p.47
43. Sakarovitch, Jacques (2009). Elementos de la teoría de autómatas . Traducido del francés por Reuben Thomas. Cambridge: Cambridge University Press . pág. 86. ISBN. 978-0-521-84425-3.Zbl 1188.68177  .

Lectura adicional

• 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. Princeton University Press, Princeton (1956); es una versión ligeramente modificada de su informe de 1951 de la RAND Corporation del mismo título, RM704.
• Sakarovitch, J (1987). "Revisión del teorema de Kleene". Tendencias, técnicas y problemas en la informática teórica . Apuntes de clase en informática. Vol. 1987. págs. 39-50. doi :10.1007/3540185356_29. ISBN 978-3-540-18535-2.

Enlaces externos

• Zoológico de la complejidad : Clase REG