Simulador de Máquina de Turing

3 Mar 2012

Este simulador de Máquina de Turing surgió a raíz de las clases de Teoría de Autómatas y Lenguajes Formales. Solo es una MT básica, no es universal.

Usa la terminal para ejecutarlo:

$ java tm.Simulator input.txt

donde input.txt tiene el siguiente formato:

aaabbb
q1, a -> q2, #, R
q2, a -> q2, a, R
q2, b -> q2, b, R
q2, # -> q3, #, L
q3, b -> q4, #, L
q4, a -> q4, a, L
q4, b -> q4, b, L
q4, # -> q1, #, R
q1, # -> qf, #, R

La primera línea es la cadena de entrada que será almacenada en la cinta. Las siguientes líneas indican las transiciones: los estados están etiquetados empezando desde q1 (el estado inicial). El estado final se etiqueta como qf y el símbolo blanco como #. Con el ejemplo anterior la máquina de Turing aceptaría cadenas del tipo anbn.

Por defecto el simulador ejecuta todas las transiciones de una vez. Para ejecutarlo paso a paso hay que añadir la opción s:

$ java tm.Simulator input.txt s

Código fuente.