301405 1070968926 Cristian Velosa PDF

Preview

Summary

UNIDAD 3 - TAREA 4 - CONSTRUCCIÓN DE MÁQUINAS DE TURINGPARTICIPANTES:CRISTIAN STIVEN VELOSA LEONCod. 1070968926GRUPO No.301405_Tutor: Vermen Rainer AyalaUniversidad Nacional Abierta y a Distancia – UNAD Escuela Ciencias básicas, tecnología e ingeniería Programa Ingeniería de Sistemas autómatas y Len...

Description

UNIDAD 3 - TAREA 4 - CONSTRUCCIÓN DE MÁQUINAS DE TURING

PARTICIPANTES: CRISTIAN STIVEN VELOSA LEON Cod. 1070968926

GRUPO No. 301405_1

Tutor: Vermen Rainer Ayala

Universidad Nacional Abierta y a Distancia – UNAD Escuela Ciencias básicas, tecnología e ingeniería Programa Ingeniería de Sistemas autómatas y Lenguajes Formales 301405 Periodo 16-04

Colombia 2020

EJERCICIOS PARA DESARROLLAR

Ejercicio Grupal: Minimización de autómatas

EJERCICIO PARA TRABAJAR

Caracterizaci ón de la máquina de turing

En este espacio se realiza: - Mediante la definición formal explicar las características de la máquina de Turing. Formalmente, una máquina de Turing se define mediante una séptupla: M= (Σ, Q, Γ, s, b, f, δ) Para el ejercicio sería de la siguiente manera Σ: {a,b,c} Γ: {a,b,c} Q: {q0, q1, q2} b ∈ Γ: {} s ∈ Q: {q0} F: {q2} δ = Transiciones δ (q0, a) = (q0,a, R) δ (q0, b) = (q0,a, R) δ (q0, a)= (q0,b,L) δ (q0, c)= (q0,a,R) δ (q1,b) = (q1,a, R)

La MT es transductores - Realizar un cuadro donde explique las diferencias y similitudes de las máquinas reconocedoras y Tras ductoras. M. RECONOCEDORA Capaz de reconocer o aceptar un lenguaje L MT capaz de aceptar un lenguaje L.

Una MT RECONOCE un lenguaje L, si dada una entrada (w) en la cinta, la MT SIEMPRE se para, y lo hace en un EF si y sólo si: w ∈ L Así, en este caso, si w ∉ L, la MT podría no parar. Ejs: MT que reconoce el lenguaje a*b*, MT que acepta el lenguaje anbncn …

M. TRANSDUCTORA Modifica el contenido de la cinta realizando cierta función Modifica el contenido de la cinta realizando cierta función. Ejs: MT que sustituye los dígitos por cero, MT que añade un bit de paridad a la entrada, MT que duplica el número de 1s que hay en la cinta … Si la Entrada está bien formada: debe terminar en un Estado Final

Modifica el estado de la cinta realizando cierta función....