Page 93 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

93

celda actual, solo si la transición es una operación de escritura; si no lo es, entonces será o’ l’ o
‘r’ si la transición es una operación de movimiento.

Así las cosas la transición Δ (P, X) = (Q, Y) estaría representado por un arco con etiqueta X/Y; o
Δ (P, X)= (Q, L) deberá aparecer un arco de P a Q con etiqueta X/L.

Obsérvese que en la primera x / y, indica que estando leída una x en la cinta, será reemplazada
por una y, la otra transición: x/l indica que siendo leído el símbolo x mueve la cabeza lectura.
Escritura a la izquierda (left). Quede claro que las operaciones de MT son escritura o movimiento,
mismo que puede ser a la derecha ® o a la izquierda (l).

Ejemplo: MT con símbolos de cinta (a,b,∆) que mueve su cabeza hacia la derecha hasta encontrar
un espacio en blanco.

A/R

△/△

B/R

Definición formal de una MT:
Una máquina de Turing es una séxtupla de la forma: MT= (S, ∑, Г, Δ, H, ) donde:

S → Colección finita de estados.
∑ → Conjunto finito de símbolos distintos de espacio en blanco llamado alfabeto de la
máquina
Г → Conjunto de símbolos finito incluidos los de ∑, conocidos como símbolos de cinta de la
maquina
Δ → Función de transición de la máquina
→ Es un elemento de s y constituye el estado inicial de la máquina

H → Es un elemento de s llamado estado de parada.
→ El espacio en blanco pertenece al conjunto de símbolos de cinta, pero no forma parte
del alfabeto de la maquina

Los símbolos de cinta de una Máquina de Turing pueden incluir marcas especiales que no sean
símbolos del alfabeto de la máquina.

Función de transición:

Por ejemplo, la transición Δ (Q1, A) = (Q5, B, R) provoca que la máquina pase de una
configuración:
A B B

Posición de la cabeza lectura/escritura en el estado
1