Unidad de Aprendizaje
"Teoría Computacional"
13-14/1 Agosto - Diciembre 2013
ESCOM IPN - ISC Plan 2003
13-14/1 Agosto - Diciembre 2013
ESCOM IPN - ISC Plan 2003
Construir un programa en ANSI C capaz de recibir como entrada dos cadenas de longitud menor a 50 caracteres alfanuméricos. El programa deberá de permitir seleccionar entre operar ambas cadenas o con solo una de ellas. El resultado de la operación entre cadenas generará una nueva cadena con la que se podrá operar posteriormente, excepto para las operaciones que generan una lista de cadenas.
Construir un programa en Python capaz de recibir como entrada tres archivos con palabras separadas por espacio (alfabeto alfanumérico), cada archivo corresponde a un lenguaje dado donde las palabras de cada archivo son el conjunto finito que forma a cada lenguaje. El programa permitira realizar las diversas operaciones entre lenjuages.
Construir un programa en Python capaz de recibir como entrada tres direcciones URL, el programa deberá de ser capaz de generar dos archivos de salida, el primero de ellos contendrá todos los correos electrónicos encontrados en las páginas URL, mientras que el segundo archivo contiene todos los links presentes en las paginas URL.
Construir un programa en Python capaz de recibir como entrada un archivo con la configuración de un autómata finito no determinista de un lenguaje regular y realizar su conversión a automata finito determinista generando un archivo de salida con su configuración.
Construir un programa en Visual C# (.NET) capaz de proporcionar una interfaz gráfica a través de la cuál sea posible ingresar una gramática en formato BNF, la cual pasará primeramente por un proceso de clasificación. Si la gramática resulta estar clasificada como tipo 3 o 2, pasará a un proceso de revisión de reglas bien formadas, limpieza, eliminación de recursividad izquierda y factorización.
Construir un programa en Visual C# (.NET) capaz de proporcionar una interfaz gráfica a través de la cuál sea posible ingresar una gramática tipo 2 en formato BNF y proporcionara una séxtupla del autómata de pila correspondiente para su reconocimiento.
Construir un programa en Visual C# (.NET) capaz de proporcionar una interfaz gráfica a través de la cuál sea posible simular el funcionamiento de la maquina de Turing estándar.
Exposiciones sobre la programación empleando expresiones regulares en el Shell de UNIX, Python, Perl, Java, JavaScript, PHP y en My SQL.
Presentación de la Unidad de Aprendizaje (Introducción, unidades tematicas, formato de las evaluaciónes, tareas, practicas y acuerdos).
Se llama alfabeto a un conjunto finito, no vacío. Los elementos de un alfabeto se llaman símbolos. Un alfabeto se define por la enumeración de los símbolos que contiene; se le llama palabra o cadena a aquella formada con los símbolos de un alfabeto. Una cadena puede ser un operando por lo que es posible hablar de operaciones entre cadenas, capaces de generar nuevas cadenas bajo el mismo alfabeto.
Un lenguaje es un conjunto de palabras (cadenas) de un determinado alfabeto. Debido a que tratamos con conjuntos, es posible realizar operaciones entre estos, logrando así operar llegar a el concepto de operaciones entre lenguajes.
Un lenguaje es un conjunto de palabras (cadenas) de un determinado alfabeto. Los lenguajes más sencillos que formalmente se consideran son los lenguajes regulares. Un lenguaje regular se puede generar a partir de lenguajes básicos, con la aplicación de las operaciones de unión, concatenación y * de Kleene un número finito de veces. Los lenguajes regulares se llaman así porque sus palabras contienen "regularidades" o repeticiones de los mismos componentes.
Una definición regular es un nombre que se le da a algunas expresiones regulares, para asi hacer más fácil su utilización en expresiones subsiguientes. Las definiciones regulares se apoyan de símbolos nuevos fuera del alfabeto original para sustituir a expresiones regulares simples y formar con estas definiciones nuevas expresiones regulares.
Un autómata es un modelo matemático para una máquina de estados, que, dada una entrada de símbolos, "salta" a través de una serie de estados de acuerdo a una función de transición produciendo salidas. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer.
Un autómata finito es un modelo matemático de una máquina que acepta cadenas de un lenguaje definido sobre un alfabeto. 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. Formalmente un autómata finito es una quíntupla A = ( E, Q, f, q0, F ), donde E es el conjunto de simbolos de entrada, Q es el conjunto finito de estados, f es la función de transición (E*x Q→Q ), q0 es el estado inicial y F es el conjunto de esatdos finales.
Un autómata finito determinista AFD es un caso particular de los autómatas finitos, en el que la función de transición no presenta ninguna ambigüedad en las transiciones de estados para una entrada dada. Para todo autómata finito no determinista AFN=(E, Q, f, q1,F) se puede construir un autómata finito determinista AFD=(E, Q’, f’, q’1, F’) tal que el lenguaje reconocido por el autómata finito determinista AFD coincida con el lenguaje reconocido por el autómata finito no determinista AFN, es decir L(AFD) = L(AFN). La construcción de Thompson construye a partir de una expresión regular r un AFN que reconoce el lenguaje definido por r, esto se realiza con el objetivo de que en un algoritmo siguiente se pueda generar un AFD mínimo equivalente.
Es posible convertir cualquier automata finito no determinista en su equivalente determinista, existen muchos metodos para ello, pero aquel que emplean la operación de cerradura, mover e ir_a, es uno de los mas utiles.
La gramática es el estudio de las reglas y principios que regulan el uso de las lenguas y la organización de las palabras dentro de una oración. También se denomina así al "conjunto de reglas y principios que gobiernan el uso de un lenguaje" así, cada lenguaje tiene su propia gramática.
En 1950 el lingüista norteamericano Avram Noam Chomsky introdujo la teoría de las gramáticas transformacionales o teoría de lenguajes formales, que convirtió la lingüística en una ciencia y proporcionó una herramienta que no sólo podía aplicarse a los lenguajes naturales, sino que facilitaba el estudio y la formalización de los lenguajes para la programación de computadoras (1960). En función de la forma de sus producciones, se puede caracterizar qué tan compleja es una gramática formal. Noam Chomsky mostró que esta caracterización clasifica jerárquicamente a las gramáticas formales: Gramáticas en un nivel están incluids en los siguientes niveles y la inclusión entre niveles es propia.
El lenguaje generado por una gramática G, L(G), es igual al conjunto de las palabras en VT derivables a partir de G. Un árbol de derivación permite mostrar gráficamente cómo se puede derivar cualquier cadena de un lenguaje a partir del símbolo inicial de una gramática que genera ese lenguaje. Una gramática es ambigua cuando para una determinada cadena, se produce más de un árbol de derivación.
Las gramáticas de tipo 2 o gramáticas independientes del contexto, son las que generan los lenguajes libres o independientes del contexto. Los lenguajes libres del contexto son aquellos que pueden ser reconocidos por un autómata de pila determinístico o no determinístico. Una gramática libre de contexto (GLC), describe un lenguaje libre de contexto. Son útiles para describir bloques anidados en lenguajes de programación ya que describen su sintaxis. Son llamadas así porque el elemento no terminal del lado derecho se puede sustituir sin importar el contexto en que este.
Una gramática limpia y bien formada facilita el correcto tratamiento y detección a la hora de ser impuesta en algún lenguaje. Para poder construir una gramática adecuada se debe verificar la correcta escritura de las reglas de producción de la gramática, así como su validez. A las gramáticas que incluyen reglas con símbolos no generativos, reglas superfluas e innecesarias, se les conoce como gramáticas sucias, por otro lado las gramáticas bien formadas, además de ser limpias no incluyen reglas no generativas ni reglas de redenominación.
Una gramática libre de contexto recursiva por izquierda da lugar a algunos problemas computacionales a la hora de construir de manera descendente un árbol de derivación de una cadena, pudiendo afectar a algoritmos descendentes que caen en un bucle infinito de recursión. A su vez una gramática no factorizada, también da lugar a problemas de indeterminismo cuando varias alternativas en una misma producción comparten el mismo prefijo, ya que un algoritmo computacional no sabría cuál elegir de manera inmediata y tendrá que probar una producción y si se produce un error haría backtracking. Es posible realizar transformaciones de gramáticas para la eliminación de la recursividad izquierda e indeterminismo. Estas transformaciones no modifican el lenguaje que se está reconociendo, pero sí que cambian el aspecto de la gramática, que es en general menos intuitiva.
Un autómata de pila es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce. El lenguaje que reconoce un autómata de pila pertenece al grupo de los lenguajes libres de contexto en la clasificación de la Jerarquía de Chomsky. Un autómata de pila es esencialmente un autómata finito que posee control sobre una cinta y una pila del tipo LIFO.
Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de un CPU dentro de un computador. La máquina de Turing fue descrita por Alan Turing como una «máquina automática» en 1936 en la revista Proceedings of the London Mathematical Society. La máquina de Turing no está diseñada como una tecnología de computación práctica, sino como un dispositivo hipotético que representa una máquina de computación. Las máquinas de Turing ayudan a los científicos a entender los límites del cálculo mecánico.
Hay otros modelos de máquinas de Turing. Todos ellos son equivalentes al modelo simple (máquinas estándar). Cualquier máquina estándar puede ser simulada por una máquina de estos modelos. Una máquina M puede almacenar datos en su unidad de control (y realizar los movimientos en función de estos datos y del estado actual), además se puede considerar que la cinta de una máquina M tiene varias pistas o tramos (para almacenar distintos datos).