Representación como diagrama de estados

    Representación como diagrama de estados

Las máquinas de Turing pueden representarse mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:

∑ = {a, b, c}, posee el conjunto de estados Q = {90, 91, 92, 93, 94, 95, 96}, con las transiciones que se pueden ver. Su estado inicial es qo y el estado final es q3, el lenguaje de salida Γ = {X, Y, Z, B} siendo B el símbolo denominado "blanco". Esta máquina reconoce la expresión regular de la

forma a b c con n >= 0.

• Los estados se representan como vértices, etiquetados con su nombre en el interior.

• Una transición desde un estado a otro, se representa mediante una arista dirigida que une a estos vértices, y está rotulada por símbolo que lee el cabezal/símbolo que escribirá el cabezal, movimiento del cabezal.

• El estado inicial se caracteriza por tener una arista que llega a él y que no proviene de ningún otro vértice.

• El o los estados finales se representan mediante vértices que están encerrados a su vez por otra circunferencia.