lenguaje regular

Lenguaje formal que se puede expresar 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 sentido estricto en informática teórica (a diferencia de muchos motores de expresiones regulares modernos, que se complementan 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 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 .

Definicion formal

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 singleton { a  } es un lenguaje regular.
• Si A es un lenguaje regular, A * ( Kleene star ) es un lenguaje regular. Debido a esto, el lenguaje de cadenas vacías {ε} 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 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 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 simple de un lenguaje que no es regular es el conjunto de cadenas { a ⁿ b ⁿ | norte ≥ 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 dan técnicas para probar 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 ser generado por 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 de dos vías
7. puede ser generado por 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 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 lengua 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, particularmente aquellas 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 autores. Un libro de texto llama a la equivalencia de expresiones regulares y NFA ("1." y "2." arriba) "teorema de Kleene". ^[6] Otro libro de texto llama a la equivalencia de expresiones regulares y DFA ("1." y "3." arriba) "teorema de Kleene". ^[7] Otros dos libros de texto prueban primero la equivalencia expresiva de los AFN y los AFD ("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 "reconocibles"). idiomas"). ^{[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 describe "lenguajes racionales" y finalmente establece 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 en el que Kleene introdujo "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 llama " forma normal de Chomsky " ), ^[11] pero notó que sus "lenguajes de estados finitos" eran equivalentes a los "eventos regulares" de Kleene . ^[12]

Propiedades de cierre

Los lenguajes regulares se cierran bajo varias operaciones, es decir, si los lenguajes K y L son regulares, también lo será 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 y estrella de Kleene L ^* . ^[14] ${\displaystyle K\circ L}$
• el trío de operaciones: homomorfismo de cadenas , homomorfismo de cadenas inverso e intersección con lenguajes regulares. Como consecuencia, están cerrados bajo transducciones arbitrarias de estados finitos , como el cociente K / L con un lenguaje regular. Aún más, los lenguajes regulares están cerrados bajo cocientes con lenguajes arbitrarios : si L es regular, entonces L / K es regular para cualquier K. ^[15]
• al revés (o imagen especular) L ^R . ^[16] Dado un autómata finito no determinista para reconocer L , se puede obtener un ^autómata para LR invirtiendo todas las transiciones e intercambiando los estados inicial y final. Esto puede dar como resultado múltiples estados iniciales; Se pueden utilizar transiciones ε para unirlas.

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 LB , respectivamente:

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

Para las expresiones regulares, el problema de universalidad ya es NP-completo para un alfabeto singleton. ^[18] Para alfabetos más grandes, ese problema es PSPACE-completo . ^[19] Si las expresiones regulares se amplían para permitir también un operador cuadrático , donde " A ² " denota lo mismo que " AA ", todavía solo se pueden describir lenguajes regulares, pero el problema de universalidad tiene un límite inferior del espacio exponencial, ^{[20] [21] [22]} y de hecho está completo para el espacio exponencial con respecto a la reducción del 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 agregar 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 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 un 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 1 bits 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 los palíndromos o el lenguaje no regular pueden reconocerse ambos 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

Lenguaje habitual 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 está libre de contexto . Lo contrario no es cierto: por ejemplo, el lenguaje que consiste en todas las cadenas que tienen el mismo número de a y b no tiene contexto, pero no es 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 ^[28] o la cuantificación de la complejidad de Kolmogorov . ^[29]

Las subclases importantes de lenguajes regulares incluyen

• Lenguas finitas, aquellas que contienen sólo un número finito de palabras. ^[30] Estos son lenguajes regulares, ya que se puede crear una expresión regular que es la unión de cada palabra en el lenguaje.
• 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. ^[31]

El número de palabras en un idioma normal.

Denotemos 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 constante-recursiva ; es decir, existen una constante entera , constantes complejas y polinomios complejos tales que para cada número de palabras de longitud 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}}$

Por lo tanto, la falta de regularidad de ciertos idiomas se puede demostrar contando las palabras de una longitud determinada en . Consideremos, 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 tiene 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 lenguaje de todas las palabras binarias pares no tiene la forma , pero el número de palabras de longitud par o impar tienen 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 (ver ω-autómatas ) y a árboles (ver autómatas de árboles ).

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 el homónimo como reconocible colocado sobre un monoide que no es necesariamente libre. Howard Straubing señala en relación a 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 utilizan 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, en general, no coinciden). Esta terminología, aunque está mejor motivada, nunca tuvo éxito, y el "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 semirreloj . 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 ejemplos

Notas

1. 1. ⇒ 2. por el algoritmo de construcción de Thompson
2. 2. ⇒ 1. mediante el algoritmo de Kleene o usando el lema de Arden
3. 2. ⇒ 3. por la construcción del conjunto de potencia
4. 3. ⇒ 2. ya que la primera definición es más fuerte que la segunda
5. 2. ⇒ 4. ver Hopcroft, Ullman (1979), Teorema 9.2, p.219
6. 4. ⇒ 2. ver Hopcroft, Ullman (1979), Teorema 9.1, p.218
7. 3. ⇔ 10. según el teorema de Myhill-Nerode
8. u ~ v se define como: uw ∈ L si y sólo si vw ∈ L para todo w ∈Σ ^*
9. 3. ⇔ 11. consulte la prueba en el artículo Monoide sintáctico y consulte la página 160 en Holcombe, WML (1982). Teoría de los autómatas algebraicos . Estudios de Cambridge en Matemáticas Avanzadas. vol. 1. Prensa de la Universidad de Cambridge . ISBN 0-521-60492-3. Zbl  0489.68046.
10. Compruebe si L _A ∩ L _B = L _A . Decidir esta propiedad es NP-difícil 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: Prensa de la Universidad de Cambridge . ISBN 978-0-521-19022-0. Zbl  1250.68007.
• Eilenberg, Samuel (1974). Autómatas, lenguajes y máquinas. Volumen A. Matemática Pura y Aplicada. vol. 58. Nueva York: Academic Press. Zbl  0317.94045.
• Salomaa, Arto (1981). Joyas de la teoría del lenguaje formal . Publicación Pitman. ISBN 0-273-08522-0. Zbl  0487.68064.
• Sipser, Michael (1997). Introducción a la Teoría de la Computación . Publicación PWS. ISBN 0-534-94728-X. Zbl  1169.68300.Capítulo 1: Idiomas habituales, págs. 31–90. Subsección "Problemas decidibles relacionados con los idiomas habituales" de la sección 4.1: Idiomas decidibles, págs.
• 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, los lenguajes y la computación de autómatas . Addison-Wesley. ISBN 0-201-02988-X.
• Alfred V. Aho, 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). El manual de Oxford de lingüística computacional. Prensa de la Universidad de Oxford. pag. 754.ISBN​ 978-0-19-927634-9.
2. Mark V. Lawson (2003). Autómatas finitos. Prensa CRC. págs. 98-103. ISBN 978-1-58488-255-8.
3. Sheng Yu (1997). "Idiomas habituales". En Grzegorz Rozenberg; Arto Salomaa (eds.). Manual de lenguajes formales: volumen 1. Palabra, lenguaje, gramática . Saltador. pag. 41.ISBN​ 978-3-540-60420-4.
4. Eilenberg (1974), pág. 16 (Ejemplo II, 2.8) y pág. 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ógica y juegos infinitos: una guía para la investigación actual. Apuntes de conferencias sobre informática 2500, Springer 2002.
6. Robert Sedgewick; Kevin Daniel Wayne (2011). Algoritmos. Profesional de Addison-Wesley. pag. 794.ISBN​ 978-0-321-57351-3.
7. Jean-Paul Allouche; Jeffrey Shallit (2003). Secuencias Automáticas: Teoría, Aplicaciones, Generalizaciones. Prensa de la Universidad de Cambridge. pag. 129.ISBN​ 978-0-521-82332-6.
8. Kenneth Rosen (2011). Matemática discreta y sus aplicaciones 7ª edición. Ciencia de McGraw-Hill. págs. 873–880.
9. Horst Bunke; Alberto Sanfeliu (enero 1990). Reconocimiento de patrones sintácticos y estructurales: teoría y aplicaciones. Científico mundial. pag. 248.ISBN​ 978-9971-5-0566-0.
10. Stephen Cole Kleene (diciembre de 1951). Representación de eventos en redes nerviosas y automatización finita (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.28
14. Salomaa (1981) p.27
15. Becarios, Michael R .; Langston, Michael A. (1991). "Problemas de constructividad en algoritmos gráficos". En Myers, Jr., J. Paul; O'Donnell, Michael J. (eds.). Constructividad en Ciencias de la Computación, Simposio de verano, San Antonio, Texas, EE. UU., 19 al 22 de junio, Actas . Apuntes de conferencias sobre informática. vol. 613. Saltador. págs. 150-158. doi :10.1007/BFB0021088.{{cite conference}}: Mantenimiento CS1: varios nombres: lista de editores ( enlace )
16. Hopcroft, Ullman (1979), Capítulo 3, Ejercicio 3.4g, pág. 72
17. Hopcroft, Ullman (1979), Teorema 3.8, p.64; ver 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, p399
20. Hopcroft, Ullman (1979), Teorema 13.15, p.351
21. AR Meyer y LJ Stockmeyer (octubre de 1972). El problema de equivalencia de expresiones regulares con elevación al cuadrado requiere espacio exponencial (PDF) . 13º Simposio Anual IEEE. sobre la teoría de la conmutación y los autómatas. págs. 125-129.
22. LJ Stockmeyer; AR Meyer (1973). "Problemas verbales que requieren tiempo exponencial". Proc. 5to año. símp. sobre Teoría de la Computación (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 conferencias sobre informática. vol. 2500. Saltador. págs. 207–230. doi :10.1007/3-540-36387-4_12. ISBN 978-3-540-00388-5.
25. Furst, Merrick; Sajonia, James B .; Sipser, Michael (1984). "Paridad, circuitos y jerarquía de tiempo polinomial". Teoría de Sistemas Matemáticos . 17 (1): 13–27. doi :10.1007/BF01744431. SEÑOR  0738749. S2CID  14677270.
26. Cocinero, Stephen; Nguyen, Phuong (2010). Fundamentos lógicos de la complejidad de la prueba (1. ed. publ.). Ithaca, Nueva York: Asociación de Lógica Simbólica. pag. 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 sexto simposio anual del IEEE sobre teoría de circuitos de conmutación y diseño lógico , págs. 1965.
28. "¿Cómo demostrar que un idioma 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, computabilidad, complejidad, algorítmica, aleatorización, comunicación y criptografía. Saltador. págs. 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 Gastín (2008). "Idiomas definibles de primer orden" (PDF) . En Jörg Flum; Erich Grädel; Thomas Wilke (eds.). Lógica y autómatas: historia y perspectivas . Prensa de la Universidad de Ámsterdam. ISBN 978-90-5356-576-6.
32. Honkala, Juha (1989). "Una condición necesaria para la racionalidad de la función zeta de una lengua regular". Teor. Computadora. Ciencia . 66 (3): 341–347. doi : 10.1016/0304-3975(89)90159-x . Zbl  0675.68034.
33. Flajolet & Sedgweick, sección V.3.1, ecuación (13).
34. "Número de palabras en el idioma habitual $(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 idioma normal". 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 . Prensa académica.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 . Avances en Informática Teórica. Basilea: Birkhäuser. pag. 8.ISBN​ 3-7643-3719-2. Zbl  0816.68086.
42. Berstel y Reutenauer (2011) p.47
43. Sakarovich, Jacques (2009). Elementos de la teoría de los autómatas . Traducido del francés por Reuben Thomas. Cambridge: Prensa de la Universidad de Cambridge . pag. 86.ISBN​ 978-0-521-84425-3. Zbl  1188.68177.

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 de RAND Corporation del mismo título, RM704.
• Sakarovich, J (1987). "Revisión del teorema de Kleene". Tendencias, técnicas y problemas en informática teórica . Apuntes de conferencias sobre informática. vol. 1987, págs. 39–50. doi :10.1007/3540185356_29. ISBN 978-3-540-18535-2.

enlaces externos

• Zoológico de complejidad : Clase REG