Welcome to the "Automata and Computability" course! This course explores theoretical models of computation, including finite automata, context-free grammars, and Turing machines.
It examines how these models define the limits of computation, analyse algorithmic complexity, and apply formal logic techniques to problem-solving. It delves into computability theory, covering decidable and undecidable problems, NP-completeness, and the Chomsky hierarchy.
Learners will explore regular expressions, context-free languages, and recursive functions to understand language processing and formal grammars. Through hands-on experience with proof techniques, algorithmic problem analysis, and formal verification, this course builds a strong foundation in computational theory.
By the end, learners will develop advanced reasoning skills applicable to theoretical computer science, software development, and artificial intelligence research. Ideal for computer science students, software engineers, and researchers, this course strengthens understanding of automata, formal languages, and complexity theory.
- Introducción a la Teoría de Autómatas
Este módulo proporciona una exploración profunda de los conceptos fundamentales de la Teoría de Autómatas. Comienza con una introducción a los fundamentos teóricos y la relevancia práctica de los autómatas en la computación. Los estudiantes revisarán los autómatas finitos, centrándose en los autómatas finitos deterministas (DFA) y su estructura, funcionalidad y aplicaciones. El módulo también explora el concepto de lenguajes aceptados por los DFA, enfatizando cómo se relacionan los autómatas con la teoría de lenguajes formales y la resolución de problemas computacionales.
- Autómatas Finitos
Autómatas Finitos es un módulo fundamental en la ciencia de la computación teórica que introduce los modelos matemáticos de cálculo y sus aplicaciones en la resolución de problemas y procesamiento de lenguajes. Este módulo se centra en el estudio de máquinas abstractas y los problemas computacionales que pueden resolver. Los estudiantes aprenderán cómo diseñar, analizar e implementar autómatas finitos para reconocer lenguajes regulares y realizar emparejamiento de patrones.
- Lenguajes Regulares
Este módulo se centra en el estudio de los Lenguajes Regulares dentro del contexto de la Teoría de Autómatas. Los lenguajes regulares forman la base de la teoría de lenguajes formales y están estrechamente vinculados con los Autómatas Finitos. El módulo cubre los fundamentos teóricos de los lenguajes regulares, su caracterización a través de autómatas finitos y expresiones regulares, y las aplicaciones prácticas en áreas como el diseño de compiladores, emparejamiento de patrones y procesamiento de texto. Los estudiantes explorarán cómo manipular lenguajes regulares y probar sus propiedades y limitaciones.
- Lenguajes Independientes del Contexto
Este módulo introduce el concepto de Lenguajes Independientes del Contexto (CFLs) y su papel fundamental en la teoría de la computación y la teoría de lenguajes formales. Cubre los fundamentos teóricos, aplicaciones prácticas y representación formal de los CFLs a través de Gramáticas Independientes del Contexto (CFGs). Los estudiantes explorarán cómo se generan, manipulan y analizan los CFLs usando árboles de derivación, árboles de análisis y formas normales como la Forma Normal de Chomsky (CNF) y la Forma Normal de Greibach (GNF). El módulo también examina propiedades clave de los CFLs, incluyendo la ambigüedad, el lema de bombeo para CFLs y las propiedades de clausura. También se discuten aplicaciones prácticas en lenguajes de programación, análisis sintáctico y diseño de compiladores.
- Simplificación, Formas Normales y Propiedades de los CFLs
Este módulo introduce técnicas clave para simplificar gramáticas independientes del contexto (CFGs), incluyendo la eliminación de producciones inútiles, nullables y unitarias. También cubre la transformación de CFGs en formas normales, como la Forma Normal de Chomsky (CNF) y la Forma Normal de Greibach (GNF), que son esenciales para el análisis sintáctico y aplicaciones algorítmicas. Adicionalmente, el módulo explora propiedades fundamentales de los Lenguajes Independientes del Contexto (CFLs), incluyendo propiedades de clausura, el lema de bombeo y problemas de decisión.
- Introducción a la Máquina de Turing
Este módulo introduce la Máquina de Turing, un modelo teórico fundamental de la computación. Cubre la definición formal de una Máquina de Turing, sus componentes y su funcionamiento como dispositivo computacional. Los estudiantes explorarán diferentes enfoques para diseñar Máquinas de Turing y trabajarán a través de ejemplos de diseño para comprender sus aplicaciones. El módulo también examina el doble rol de las Máquinas de Turing: como aceptadoras de lenguajes para reconocer lenguajes formales y como transductoras para calcular funciones, demostrando su importancia en la ciencia de la computación teórica y los fundamentos de la computación.
- Variaciones de la Máquina de Turing
Este módulo explora conceptos avanzados y variaciones de la Máquina de Turing, un pilar de la teoría de la computación. Se adentra en las Máquinas de Turing con control finito, múltiples pistas, cintas infinitas bidireccionales, configuraciones multi-cinta, mecanismos multi-cabeza y modelos no deterministas, destacando sus capacidades únicas y poder computacional. Se introduce el concepto de la Máquina de Turing Universal, demostrando su papel como modelo de computación general. El módulo también examina funciones computables por Turing y sus implicaciones, culminando en una comprensión de la Tesis de Church-Turing, que formaliza los límites de la computación algorítmica y los fundamentos de la ciencia de la computación.
- Jerarquía de Lenguajes Formales y Autómatas
Este módulo examina la clasificación de lenguajes formales y su relación con modelos computacionales. Se centra en lenguajes recursivos y recursivamente enumerables, explorando sus propiedades y distinciones dentro del marco computacional. Se introduce el concepto de gramáticas no restringidas como una herramienta poderosa para generar lenguajes más allá de las clases regulares e independientes del contexto. Adicionalmente, el módulo analiza las gramáticas sensibles al contexto (CSG) y su lugar en la Jerarquía de Chomsky, proporcionando una comprensión estructurada de las clases de lenguajes y su complejidad computacional. Estos temas forman la base para analizar el poder expresivo de diferentes sistemas formales y sus aplicaciones en el mundo real.
- Computabilidad y Decidibilidad
Este módulo, parte de la Teoría de Autómatas, se centra en los conceptos fundamentales de computabilidad y decidibilidad. Los estudiantes estudiarán lenguajes formales, modelos de autómatas (autómatas finitos, autómatas de pila, máquinas de Turing) y la clasificación de problemas computacionales según su resolvibilidad. El módulo examina cómo las máquinas de Turing sirven como estándar para lo que es "computable" y explora los límites de la resolución de problemas algorítmicos mediante ejemplos de lenguajes decidibles e indecidibles. Los estudiantes participarán en razonamientos formales, pruebas y reducciones para entender los límites teóricos de la computación.
- Panorama de la Complejidad Computacional
Este módulo, integrado en la Teoría de Autómatas, introduce el estudio de la complejidad computacional, entendiendo no solo qué problemas pueden resolverse, sino también cuán eficientemente pueden resolverse. Los estudiantes explorarán modelos de computación, como las máquinas de Turing, para analizar la complejidad del tiempo y el espacio. El curso cubre clases de complejidad como P, NP y problemas NP-completos, con un enfoque en métodos formales para probar límites de complejidad. A través de ejemplos y pruebas teóricas, los estudiantes desarrollarán la habilidad para evaluar la eficiencia de los algoritmos y la dificultad intrínseca de los problemas computacionales.
