Ingenieria

INSTITUTO TECNOLOGICO SUPERIOR DE TARIMORO
EXTENSION ITESI

CARRERA

Ingeniería en Sistemas Computacionales

MATERIA

Teoría de la computación

PROFESOR

Ronald Dueñez Ortiz

TEMALenguajes Regulares

ASESOR

Laura Verónica Álvarez Holguín

ALUMNO

Juan Jesús Jiménez Sánchez

FECHA: 14 de Noviembre del 2010.

Actividades:

1. Describir máquinas de Turing quelleven a cabo las siguientes tareas:
* Dados dos números naturales m; n ε N, calcula su suma m + n.
* Dados dos números enteros m; n ε N, decide si m ≥ n.
* Dados dos números naturales m; nε N, calcula su resta m-n siempre y cuando m ≥ n.
* En caso contrario, i. e. m < n, la máquina rechaza la entrada.
* Dados dos números naturales m; n ε N, calcula su producto m - n.
*Dados dos números naturales m; n ε N, calcula el cociente y el resto de dividir m por n siempre y cuando m ╪ 0. En caso contrario, i. e. si m = 0, la máquina rechaza la entrada.
* Dados dos númerosnaturales m; n ε N, calcula su suma m + n.

Una forma simple de representar los números naturales es utilizando tantos símbolos como indique su valor numérico. Es decir, si hay que sumar 2 y 3, sepodrían representar, respectivamente, como 11 y 111. Para separar ambos sumandos se podría utilizar un 0. Así, la cinta de entrada del autómata podría tener el siguiente aspecto,0011011100000BBBBBBBBB…

Puesto que 11+111 = 11111, una posible forma de realizar el cálculo si el cabezal estuviera sobre la primera celda sería: primero, localizar el primer sumando (es decir, localizar el primer 1)y, segundo, eliminar ese primer 1 del primer sumando con un 0 y avanzar hasta encontrar el 0 de la separación y sustituirlo por un 1. Se obtendría como cadena de salida,
0001111100000BBBBBBBBB…Para ello, el autómata debe obedecer a la función de transición:
 

| 0 | 1 |
Q0 | (q0,0,R) | (q1,0,R) |
Q1 | (q1,1,R) | (q1,0,R) |
Q2 | (q2,2,R) | (q1,0,R) |

Ejercicio 2
Diseñe una...