¿Dónde puedo encontrar autómatas de muestra y máquinas de turing? [cerrado]

Question

Estoy estudiando para una prueba de autómatas en un curso que se basa en gran medida en jflap. El problema es que no tenemos mucha documentación y los autómatas de muestra que he encontrado en jlap como this y this , son insuficientes para Prepárate para la próxima prueba.

¿Dónde puedo encontrar más? Cualquier otro recurso con máquinas turing de muestra que se muestran como gráficos con transiciones también sería útil.

Answer 1

" Resolución de problemas en autómatas, lenguajes y complejidad " es un libro de texto fantástico para todo lo relacionado con ... cualquier cosa en su título. Entre otras cosas, puede encontrar un montón de ejemplos de DFA / NFA / PDA / TM para todo tipo de cosas, y le enseñan muchas técnicas para construirlos.

Editar: ese primer enlace suyo sigue hablando de " NPDA no deterministas " y " NPDA deterministas " ;. Estoy escribiendo esta edición solo para satisfacer mi impulso de denunciar tales pleonasmos y oxímora :)

Answer 2

Pruebe el excelente libro de Michael Sipser " Introducción a la teoría de la computación " . Los autómatas y las máquinas de Turing se expresan como diagramas de estado, con suficiente explicación de texto para ayudarlo a interpretarlos e implementarlos.

Este fue nuestro texto del curso en Uni hace aproximadamente 4 años, justo antes de que saliera la segunda edición; fue una verdadera roca, ¡lo recomiendo de todo corazón!