• Author / Uploaded
• Sertgio Zapata Espinosa

Citation preview

Autómatas y Lenguajes formarles Fase 4 Modelar problemas de Lenguajes Estructurados por Frases Tutor Vermen Rainer Ayala

Grupo

301405_31

Por:

Sergio Zapata Espinosa Código71718620

20/04/2020 CEAD Medellín

Introducción Por medio del presente trabajo se pretende adquirir las habilidades en la construcción de gramáticas y autómatas por medio de los mecanismos de representación formal, profundizando en el funcionamiento de las maquinas de Turing, tesis de church/turing resolviendo problemas decidibles e insolubles para la teoría de lenguajes y funciones recursivas.

Actividades Individuales:

Cada estudiante resuelve el taller propuesto en el objeto virtual de aprendizaje lenguajes estructurados por frases propuesto en el entorno de conocimiento Unidad 3. De acuerdo al último dígito de su cédula o tarjeta de identidad, identifique el ejercicio asignado en la siguiente tabla: Último dígito Ejercicio de la Cédula o TI 1y9 Ejercicio 1 2y8 Ejercicio 2 3y7 Ejercicio 3 4y6 Ejercicio 4 5y0 Ejercicio 5

Actividad 1: Máquinas de Turing El diseño solicitado corresponde al diligenciamiento de la siguiente tabla:

EJERCICIO A TRABAJAR

Registre aquí el Ejercicio a trabajar. Por favor agregue la imagen

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.

Definición Formal  

Formalmente, una máquina de Turing se define mediante una septupla: M= (Σ,Q,Γ,s,b,f, δ)  donde : Σ:es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina o de entrada Γ: es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta (Σ, ⊆Γ ) Q: es un conjunto finito de estados b ∈ Γ: es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces s ∈ Q: el estado inicial del autómata F ⊆ Q: es el subconjunto de estados finales  δ = (Q * Γ) -> (Q *  Γ * L, R ) denominada función de transición, donde L es un movimiento a la izquierda y R es el movimiento a la derecha. Σ:{0, 1} Γ: {0, 1} Q: {q0, q1, q2, q4} b ∈ Γ: Ц s ∈ Q: {q0} F ⊆ Q: {q4} δ = (Q * Γ) -> (Q *  Γ * L, R ) Transiciones σ =( q 0,0 )=( q 0,0 , R) σ =( q 0,1 ) =(q 0,1, R) σ =( q 0 , λ )=( q 1, λ , L) σ =( q 1,0 ) =(q 2,1, L) σ =( q 2,1 )= ( q 2,1 , L ) σ =( q 2,0 ) =( q 2,0 , L ) σ =( q 2 , λ )=(q 4 , λ , R)

-

Realizar un cuadro donde explique las diferencias y similitudes de las máquinas reconocedoras y Trasductoras DIFERENCIAS

Maquinas Reconocedoras Resuelven problemas con respuesta si/no, que se modeliza normalmente como la identificación de dos estados finales, uno de aceptación y el otro de rechazo

Maquinas Trasductores Construyen una respuesta específica (una salida) para el problema planteado.

Nos indican si un conjunto de símbolos pertenece o no al lenguaje

Nos entregan como resultado un conjunto de símbolos que pertenecen al lenguaje

Decidir si la cadena es válida o no, según algún criterio

Transformar la entrada

Si la palabra no pertenece al lenguaje no se exige a la MT que se detenga

Debe acabar en estado no final para indicar el error en la entrada

Dos conceptos: RECONOCER, ACEPTAR - Una Máquina de Turing RECONOCE un lenguaje L, si para cualquier entrada en la cinta, w, se acaba parando, y lo hace en un estado final si y sólo siw ∈ L.

Realiza un cálculo: - Si la entrada está bien formada, debe terminar en un estado final.

- Una Máquina de Turing ACEPTA un lenguaje L si, al

- Si la entrada NO está bien formada, debe terminar en un estado no final.

analizar una palabra w, se para en un estado final si y sólo siw ∈ L

Procedimiento de paso a paso del recorrido de una cadena

Realice de manera detallada y grafica el procedimiento paso a paso del recorrido de una cadena (La cadena la selecciona el estudiante, debe contener como mínimo 10 caracteres) en la máquina de turing. Describir cómo funciona el almacenamiento mediante el uso de las cintas, etc. Cadena Aceptada: 1100110000

Gráfico

Paso 1

q0 Transición

σ =( q 0,1 ) =(q 0,1, R)

Estando en estado 𝑞0, la cabeza de la MT señala el símbolo “1” de la cinta lee “1” y se desplaza hacia la derecha

Paso 2

q0 σ =( q 0,1 ) =(q 0,1, R)

Estando en estado 𝑞0, la cabeza de la MT vuelve a leer el símbolo “1” de la cinta, escribe “1” y se desplaza hacia la derecha Paso 3

q0 σ =( q 0,0 )=( q 0,0 , R)

Estando en estado 𝑞0, la cabeza de la MT lee el símbolo “0” de la cinta, escribe “0” y se desplaza hacia la derecha Paso 3

q0 σ =( q 0,0 )=( q 0,0 , R)

Estando en estado 𝑞0, la cabeza de la MT lee el símbolo “0” de la cinta, escribe “0” y se desplaza hacia la derecha

Paso 4

σ =( q 0,1 ) =(q 0,1, R) σ =( q 0,1 ) =(q 0,1, R) σ =( q 0,0 )=( q 0,0 , R) σ =( q 0,0 )=( q 0,0 , R)

q0

Mientras la MT lea “1” y “0” permanecerá indefinidamente en estado 𝑞0 y se desplazara hacia la

derecha en la cinta hasta la casilla que se encuentra vacía. Paso 5

q1 σ =( q 0 , λ )=( q 1, λ , L)

Estando en estado 𝑞0, la cabeza de la MT No lee nada, casilla vacía de la cinta,se desplaza a la izquierda quedando en 𝑞1 Paso 6

σ =( q 1,0 ) =(q 2,1, L)

q2

Estando en estado 𝑞1, la cabeza de la MT lee el símbolo “0” de la cinta, escribe “1” y se desplaza hacia la izquierda quedando en 𝑞2.

Paso 7

q2

σ =( q 2,0 ) =( q 2,0 , L) σ =( q 2,0 ) =( q 2,0 , L) σ =( q 2,1 )=(q 2,1 , L) σ =( q 2,1 )=(q 2,1 , L) Mientras la MT lea “1” y “0” permanecerá indefinidamente en estado 𝑞2 y se desplazara hacia la

izquierda en la cinta hasta la casilla que se encuentra vacía.

Paso 7

q2

σ =( q 2 , λ )=(q 4 , λ , R)

Estando en estado 𝑞2, la cabeza de la MT No lee nada, casilla vacía de la cinta, y se desplaza a la derecha quedando en 𝑞4 estado final

Practicar y verificar lo aprendido

Apoyándose en el simulador JFlap o VAS ejecutar y validar por lo menos cinco cadenas válidas y 5 cadenas rechazadas por la máquina. En este espacio adjunta la imagen.

Actividad 2:

Teniendo en cuenta la siguiente tabla de transición de una máquina de Mealy, realice: f Estado q0 q1 q2 q3

G

Entrada 0 1 q1 q0 q2 q0 q3 q2 q2 q1

Entrada

Estad o q0 q1 q2 q3

0 1 0 1 0

1 1 1 0 0

1. Identifique los componentes de la Máquina (descríbala). La máquina de Mealy es una 6 tupla

MM={S , S 0, Σ , Λ ,T ,G }

Σ = Alfabeto de Entrada S = Conjunto finito de estados S0 = Estado Inicial Λ = Alfabeto de Salida T : S x Σ → S=¿Función de Transición G :S x Σ→ Λ = Función de Salida Σ ={0, 1} S = {q0, q1, q2, q3}

S0 = {q0} Λ = {0,1}

Transiciones T =( q 0,0 )=( q 1) T =( q 0,1 ) =( q 0) T =( q 1 , 0 )=(q 2) T =( q 1 , 1 )=( q 0) T =( q 2 , 0 ) = ( q 3 ) T =( q 2 , 1 )= ( q 2 ) T =( q 3 , 0 ) =(q 2) T =( q 3,1 ) =(q 1)

2. Diséñela en diagrama (Máquina de Mealy).

q1

0:1

0:0 1:0

1:1

q0

1:1

1:0 q2

0:1 0:0 q3

3. Recorra la máquina con al menos una cadena válida explicando lo sucedido tanto en la cinta como en la secuencia de entrada. Cadena valida:101001011

Automata en q0 lee 1 y queda en q0 la cinta marca 1 1

Ingresa 0 a q0 automata se desplaza a q1 la cinta marca 1

1 1

Ingresa 1 en q1 automata se desplaza a q0 la cinta marca 1 1 1

1

Estando en q0 ingresa 0 automata de desplaza a q1 y cinta marca 1

1 1

1

1

Estando en q1 ingresa 0 automata de desplaza a q2 y cinta marca 0 1 1

1

1

0

Estando en q2 ingresa 1 automata queda en q2 y cinta marca 0 1 1

1

1

0

0

Estando en q2 ingresa 0 automata se desplaza a q3 y cinta marca 1 1 1

1

1

0

0

1

Estando en q3 ingresa 1 automata se desplaza a q1 y cinta marca 0 1 1

1

1

0

0

1

0

Estando en q1 ingresa 1 automata se desplaza a q0 y cinta marca 1 1 1

1

1

0

0

1

0

1

Cadena valida

Verificación en JFlap

4. Realice la conversión paso a paso de máquina de Mealy a máquina de Moore

5. Explique cinco características de la Máquina de Mealy y encuentre cinco diferencias con las Máquinas de Moore.

Máquina de Mealy

Maquina d Moore

La salida depende tanto de la situación actual y entrada

La salida solo depende de la situación actual

La máquina de Mealy ejecuta más rápido a las entradas

Necesita más lógica para decodificar las salidas

La salida cambia en los extremos de reloj

El cambio de entrada causa cambio en la salida debido a la lógica

Presenta menos estados que la máquina de Moore

Presenta más estados que la máquina de Mealy

Las salidas son función del estado y de las entradas

Las salidas son función únicamente del estado

Presenta un circuito sumador

Presenta un sumador serial

PREGUNTAS VERIFICACION OVA

La máquina de Turing creada en el ejemplo es una maquina es: A. Máquina transductora B. Maquina reconocedora C. Maquina calculadora D. Máquina estabilizadora   2. En la máquina de Turing creada de ejemplo el símbolo que representa la cita es: A.      1 B.      A C.      L D.      a 3. En la máquina de Turing creada de ejemplo la cadena que se ejecuta es: A.   aa B.   aab C.   baa D.   ab 4. En el ejercicio desarrollado es el video de Códigos Convolucionales Tellis y Viterbi la cadena que se utiliza es: A.  10100110 B.  10010110 C.  11010010 D.  01011001

Conclusiones Por medio del

trabajo realizado se adquirieron las habilidades y el conocimiento en la

construcción de gramáticas y autómatas por medio de los mecanismos de representación formal, profundizando en el funcionamiento de las maquinas de Turing, tesis de church/turing resolviendo problemas decidibles e insolubles para la teoría de lenguajes y funciones recursivas.

Referencias Bibliográficas

Carrasco, R., Calera, R., Forcada, M. (2016). Teoría De Lenguajes, Gramáticas Y Autómatas Para Informáticos. (pp. 119 - 127). Recuperado de http://bibliotecavirtual.unad.edu.co:2051/login.aspx? direct=true&db=nlebk&AN=318032&lang=es&site=edslive&ebv=EB&ppid=p p_Cover Hernández, R. (2010). Practique la teoría de autómatas y lenguajes formales. (pp. 1 - 124). Recuperado de http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action? docID=10566114&ppg=10 Alfonseca C, E., Alfonseca M, M., Mariyón S, R. (2009). (pp. 249 276). Teoría de autómatas y lenguajes formales. Recuperado de http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action? docID=10498456&ppg=6 Millán, J., Antonio J. (2009). Compiladores y procesadores de lenguajes. (pp. 73 - 126). Recuperado de http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/detail.action? docID=10844351 González, A. [Ángela] (2017, mayo 16). Minimización de un autómata. [Archivo de video]. Recuperado de González, A. [Ángela]. (2018, junio 1). Lenguajes Independientes del Contexto. [Archivo web]. Recuperado de http://hdl.handle.net/10596/18317 CK-12, (2014). Connecting Science and Mathematics to Engineering.  [OVI]. Recuperado de   http://www.ck12.org/book/Engineering%3A-AnIntroduction-for-High-School/section/5.3/ Hernández Rodríguez, L. A. (2012). Practique la teoría de autómatas y lenguajes formales. Retrieved from http://bibliotecavirtual.unad.edu.co/login? url=http://search.ebscohost.com/login.aspx? direct=true&db=edselb&AN=edselb.3199845&lang=es&site=edslive&scope=site