aaaa

DIVISIÓN.
INGENIERÍA EN SISTEMAS COMPUTACIONALES
GRUPO.
352-M
ASIGNATURA.
LENGUAJES Y AUTÓMATAS I
DOCENTE.
-
NOMBRE DEL ALUMNO.
NO. DE CONTROL.
FECHA
Nº ACTIVIDAD
AGUILAR MARTINEZ ENRIQUE
GARCIA GONZALEZ CARLOS BRANDON
HERNÁNDEZ LARA FELIPE
123107095
123107155
123107115
20-OCTUBRE-2014



PRODUCTO.
TEMARIO UNIDAD IV (MAQUINA DE TURING)
CALIFICACIÓN Y FIRMA DELPROFESOR.


INDICE

MAQUINA DE TURING

2
3
4
4.1 Definición formal de una máquina de Turing (MT) 2
4.2 Construcción modular de una máquina de Turing (MT) 4
4.3 Lenguajes aceptados por la máquina de Turing (MT) 5
4.4 Referencias Bibliográficas 9















4.1 Definición formal de una máquina de Turing (MT)
La Máquina de Turing (MT) fue introducida por Alan M.Turing en 1936, y puede considerarse
como un modelo abstracto que formaliza la idea Intuitiva de algoritmo.



(MT) Es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma. Este modelo está conformado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (normalmente b, Δ o0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados.

 
Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual es finita por la izquierda) pertenecientes al alfabeto de entrada. Luego va leyendo una celda de la cinta, borrando el símbolo, escribir el nuevo símbolo perteneciente alalfabeto de salida y finalmente avanza a la izquierda o a la derecha (solo una celda a la vez), repitiendo esto según se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.



Está constituida por los siguientes elementos:
MT = (E, A, B, e0, F, f)
E = Conjunto de estados, no vacío.
A = Conjunto de símbolos de entrada.
B= Conjunto de símbolos auxiliares.
e0 = Estado inicial.
F = Conjunto de estados finales.
f  = Función de control, definida:

Dónde:   f: (E - F)   x   (A È B)   Þ   E x  (A È B)   x   (I, O, D)
I = movimiento del cabezal a la izquierda.
O = movimiento nulo.
D = movimiento a la derecha.
La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal leeel contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:
Avanzar el cabezal lector/escritor para la derecha.
Avanzar el cabezal lector/escritor para la izquierda.

4.2 Construcción modular de una máquina de Turing (MT).
El objetivo de la creación modular de una máquina de Turing es poder desarrollar máquinascomplejas a partir de bloques elementales, a partir de máquinas más pequeñas, mediante diagramas de transiciones. La construcción de máquinas de Turing se lleva a cabo mediante los diagramas de transición y combinarlos de manera parecida a lo que se realiza en la formación de la unión y concatenación de los autómatas finitos.
 
Pasos para la construcción de una máquina de Turing:
Elimine lascaracterísticas de inicio de los estados iniciales de las maquinas, excepto la de aquel donde iniciara la maquina compuesta.
Elimine las características de detención de los estados de parada de todas la maquinas e introduzca un nuevo estado de parada que no se encuentre en ninguno de los diagramas que se combinan.
Para cada uno de los antiguos estados de parada p y cada x en y.



Una máquina deTuring es un autómata que se mueve sobre una secuencia lineal de datos.  En cada instante la máquina puede leer un solo dato de la secuencia (generalmente un carácter) y realiza ciertas acciones en base a una tabla que tiene en cuenta su "estado" actual (interno) y el último dato leído.
 
Entre las acciones está la posibilidad de escribir nuevos datos en la secuencia;  recorrer la secuencia en...