Act 14: Trabajo Colaborativo Unidad No. 3

Act 14: Trabajo Colaborativo Unidad No. 3

HUIL SEBASTIAN CAMACHO - CC:

GLORIA MARLEN RAMIREZ CAMELO – CC: 1074556124

Luis Alberto Jaramillo González - C.C.: 1151958462

JAIME JOSE VALDES

TUTOR

Universidad Nacional Abierta y a Distancia UNAD

Escuela de ciencias básicas, tecnología e ingeniería

Agosto 2014

INTRODUCCIÓN

OBJETIVOS

Tabla de Contenido

Introducción 2

Objetivos 3

Ejercicio 1 5

Ejercicio 2 11

Bibliografía 17

EJERCICIO 1

Diseñe una MT con los símbolos de la cinta x, y y que se detenga si y solo si reconoce la cadena xyxy

1. Identifique los componentes de la Máquina de Tur ing (descríbala).

Una MT es un séptuplo (K, Σ, , , s) en donde:

K Conjunto de estados tal que h ϵ K K = {o0, o1, o2, o3, o4}

∑ Alfabeto de entrada donde Ц ∉ ∑

∑ = {x, y}

┌ Alfabeto de la cinta, donde Ц ∈ ┌ y ∑ ⊆ ┌ ∑ = {0,1}

S ϵ K Es el estado inicial

s = o0

T⊆ K Es el estado final

f = o4

B⊆ ┌ Es el símbolo blanco (el símbolo B no puede hacer parte de ∑ ) aparece en todas las casillas excepto en aquellas que contienen los símbolos de entrada. B = ⌀

σ : (K – {h} x ┌ ) → K x ( ┌ U { L,R } ) σ: {00, x} = {00, x, L}

σ: {00, x} = {01, 0, R}

σ: {01, y} = {02, 1, R}

σ: {02, x} = {03, 0, R}

σ: {03, y} = {04, 1, R}

σ: {00, x} = {00, x, L}

σ: {01, x} = {00, x, L}

σ: {02, y} = {00, y, L}

σ: {03, x} = {02, x, L}

2. Diséñela en un Diagrama de Moore

3. Recorra la máquina con al menos una cadena válida.

4. Identifique una cadena que no sea válida y justi fíquela porque.

La cadena no es válida ya que al ser leída termina cayendo en un ciclo donde solo va leer espacio en blanco y por tal no podrá c ontinuar.

5. Ejecute el RunTest a la cadena aceptada (muéstrela en la captura de imagen para el trabajo)

6. Identifique en qué momento la máquina se detiene

La maquina se detiene en el momento que ha leído “xyxy” como se evidencia en la grafica.

EJERCICIO 2

Tomando como referencia la aplicabilidad de las máquinas de estados, la Teoría de la Información trata una de las técnicas de detección y corrección de errores, por los teoremas de Trellis

...