Libros sobre teoría de autómatas para el autoestudio

Necesito un libro de teoría de autómatas finito con muchos ejemplos que pueda usar para el autoaprendizaje y para prepararme para los exámenes.

La referencia clásica es " Introducción a la teoría de autómatas, idiomas y computación " (por Hopcroft, Motwani y Ullman). Algunas personas también recomiendan los " Idiomas formales y su relación con los autómatas ", mucho más antiguos (de Hopcroft y Ullman).

Sin embargo, me gusta " Introducción a la teoría de la computación " (por Sipser). Está muy bien escrito y es un libro relativamente nuevo.

Tengo un punto débil para Automata & Computability de Dexter Kozen ( tabla de contenido y capítulos de muestra [PS]). Es bastante completo y cubre algunos temas avanzados realmente interesantes. Las pruebas son formales y explícitas y la notación y el formato son encantadores. Lo más importante, los ejercicios son excelentes, por lo que dependiendo del nivel de sus exámenes, será un buen material de estudio.

El que más uso para mis cursos es Elements of Automata Theory de Jacques Sakarovitch, Cambridge University Press, 2009. Su alcance podría ser un poco diferente al de los demás, ya que también cubre ampliamente aspectos algebraicos, series de poder formal, y transducciones. Y hay muchos ejercicios.

"Combinatoria aplicada en palabras", por Lothaire, 2004

Es de lejos mi favorito. Un montón de ejemplos, y también se acumula desde lo básico absoluto hasta algunas aplicaciones de autómatas bastante interesantes, como el reconocimiento automático de voz con transductores de estado finito ponderado y temas de bioinformática.

Lo mejor de todo, es de descarga gratuita y también incluye conjuntos de soluciones:

http://www-igm.univ-mlv.fr/~berstel/Lothaire/

"Solución de problemas en autómatas, idiomas y complejidad" de Du-Ko es uno de mis favoritos después de Sipser, HU y Kozen. Contiene muchas soluciones a los problemas * rd de Kozen y sipser con numerosos ejemplos y ejercicios relacionados. Especialmente útil para la preparación de exámenes.

No estoy seguro de que este sea el mejor libro para prepararse para los exámenes, pero el libro

Autómatas finitos; Comportamiento y síntesis de BA Trakhtenbrot y Ya. M. Barzdinʹ

es bastante bueno Tiene una sorprendente cantidad de excelentes resultados que he encontrado especialmente útiles en la investigación.

Introducción a los lenguajes y la teoría de la computación.

John C. Martin

Recomiendo encarecidamente este libro para principiantes y es una elección perfecta para alguien que busca muchos ejemplos.

Disfruto de las siguientes notas de clase de Jarkko Kari: http://users.utu.fi/jkari/automata/

Breve resumen del curso:

Regular languages
    Finite automata, regular expressions
    Kleene theorem
    Pumping lemma
    Closure properties and decision algorithms
    State minimization, Myhill-Nerode theorem

Context-free languages
    Grammars, parsing
    Normal forms
    Pushdown automata
    Pumping lemma
    Closure properties and decision algorithms

Turing machines
    Recursive and recursively enumerable languages
    Universal Turing machines
    Undecidability of the halting problem (Turing)
    Reductions, other undecidable problems

También hay Elementos de la teoría de la computación de H.Lewis y C.Papadimitriou. Es una introducción bien escrita a la teoría de autómatas.

Comprensión de la computación

De máquinas simples a programas imposibles

Cubre muchas cosas, que incluyen la teoría de autómatas. Los ejemplos se presentan en Ruby, y son bastante fáciles de entender. Es posible que necesite otro libro si desea profundizar en la teoría, pero este es excelente para aprender los conceptos básicos.

"Lenguajes formales y teoría de autómatas" de AA Puntambekar es el mejor libro para ejemplos resueltos. La mayor parte del libro contiene solo ejemplos resueltos y poca teoría. Es bueno aprobar los exámenes.