• Author / Uploaded
• luna cali

• Categories
• Teoría de autómatas
• Alan Turing
• Lenguaje de programación
• Formalismo (deductivo)
• Áreas de informática

Citation preview

AUTOMATAS Y LENGUAJES FORMALES FASE 1. PRE SABERES

Presentado por WILFREDO TORRES CODIGO: 80119294

Presentado a ANGELA MARIA GONZALEZ TUTORA

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD ESCUELA DE CIENCIAS BASICAS TECNOLOGIA E INGENIERIA SEPTIEMBRE 2019 TUNJA

Actividad 1: Realizar una línea del tiempo que permita observar cronológicamente la historia y evolución de la teoría de autómatas y lenguajes formales, se debe tener en cuenta los orígenes, los precursores y los distintos campos en los que repercute esta área del conocimiento (Ingeniería, lenguajes y gramáticas, matemáticas y computabilidad) y aplicación directa de las ciencias computacionales. Link de la actividad desarrollada en prezi https://prezi.com/qddezyyv1b--/?utm_campaign=share&utm_medium=copy

Actividad 2: Realizar un resumen, ensayo o relatoría (El estudiante selecciona uno a trabajar) sobre Alan Turing y la máquina enigma, existen varios documentales y películas que cuentan esta historia, adicional pueden realizar búsquedas en la biblioteca virtual de la universidad sobre el tema. Para saber que estructura tiene cada uno de los textos académicos solicitados tener presente el siguiente autor: http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action?docID=1045828 7&ppg=9

Esta película trata del descifrado de los códigos secretos nazis, la historia de Alan Turing, y la creación de “Christopher” y los problemas que esta misma presento. además de esto trata sobre la vida de Turing que no fue sencilla debido a su gran intelecto, esto mismo ayudo a que la maquina pudiera ser construida. Viéndolo desde el lado de la programación, esta película es una perfecta ilustración a una frase muy usada en el mundo de la seguridad informátic a, “Ninguna maquina o programa creado por el ser humano está libre de fallas,” lo cual da alusión a que todo tiene una vulnerabilidad. Aquí Turing seria el “hacker” que está tratando de “romper” el algoritmo de Enigma con la ayuda de su máquina, siendo que la vulnerabilidad de Enigma sería un el cual termina con la misma frase todos los días. El Código Enigma, película dirigida por Morten Tyldum, trata sobre Alan Turing y un grupo de cripto analistas quienes buscan descifrar el código de la maquina Enigma. Esta máquina es creada por los Nazis para crear mensajes encriptados con el propósito de poder comunicarse entre ellos. Turing, junto a otros destacados miembros, es reclutado con el fin de ayudar con el descifrado del

código Enigma. Mientras los otros miembros de su equipo buscan descifrar un mensaje a la vez. Turing se enfoca en crear una maquina capaz de romper el cifrado de la máquina. Esta película se centra en tres puntos importantes: la máquina que crea el código Enigma, Turingy su pasado, y la maquina creada por Turing. Enigma es el nombre de la máquina que fue adoptada por los militares alemanes. Esta máquina contaba con un mecanismo de cifrado rotatorio el cual servía para cifrar y descifrar mensajes. Los operadores de Enigma daban un mensaje en texto plano a encriptar, por cada letra tecleada en la maquina una lámpara se encendía en el panel mostrando una letra diferente a la original basada en una sustitución pseudo-aleatoria. Al mismo tiempo, cada vez que se presionaba una tecla los rotores se movían para que la siguiente letra utilizara otra vía eléctrica lo cual producía una sustitución diferente Actividad 3: El estudiante busca 3 libros, revistas, artículos, entre otros en la biblioteca de la universidad que no se encuentren en las referencias bibliográficas del syllabus donde se encuentre el tema estudiado anteriormente. Debe agregar la referencia bajo norma APA. Presenta una síntesis de cada una de ellas. ➢ Lo que busca dar a conocer este libro sobre los autómatas y lenguajes formales es dar la explicación al termino en si que se utiliza en este tema como lo son los autómatas y lenguajes formales tambien nos muestra las diferentes clasificaciones que tienen los autómatas y lenguajes formales y tambien las expresiones y los lenguajes que se deben tener en cuenta al momento de abordar el tema. “García Fernández, L. A., & Martínez Vidal, M. G. (2009). Apuntes de Teoría de Autómatas y Lenguajes Formales. Recuperado de http://search.ebscohost.com.bibliotecavirtual.unad.edu.co/login.aspx?direct =true&db=edsbas&AN=edsbas.FEF5F46&lang=es&site=edslive&scope=site” ➢ Un lenguaje regular es un lenguaje formal que tiene estas características: Puede ser descrito mediante una expresión regular (expresar de forma compacta cómo son todas las cadenas de símbolos que le pertenecen) Puede ser generado mediante una gramática regular (obtener todas las cadenas de símbolos que le pertenecen) Puede ser reconocido mediante un autómata finito (saber si una cadena de símbolos pertenece a él o no) “ÁLVAREZ VARGAS, G. I. (2008). Estudio de la mezcla de estados determinista y no determinista en el diseño de algoritmos para inferencia gramatical de lenguajes regulares. Retrieved from

http://search.ebscohost.com.bibliotecavirtual.unad.edu.co/login.aspx?direct =true&db=edsbas&AN=edsbas.A6C613FD&lang=es&site=edslive&scope=site” ➢ Un autómata finito es un modelo matemático de una máquina que acepta cadenas de un lenguaje definido sobre un alfabeto A. Consiste en un conjunto finito de estados y un conjunto de transiciones entre esos estados, que dependen de los símbolos de la cadena de entrada. El autómata finito acepta una cadena x si la secuencia de transiciones correspondientes a los símbolos de x conduce desde el estado inicial a un estado final. Si para todo estado del autómata existe como máximo una transición definida para cada símbolo del alfabeto, se dice que el autómata es determinístico (AFD). Si a partir de algún estado y para el mismo símbolo de entrada, se definen dos o más transiciones se dice que el autómata es no determinístico (AFND) “Bondía, J., & Roa, P. (2016). Una forma canónica para autómatas finitos. Retrieved from http://search.ebscohost.com.bibliotecavirtual.unad.edu.co/login.aspx?direct =true&db=edsbas&AN=edsbas.5DD91B37&lang=es&site=edslive&scope=site”