En esta serie de artículos, se introducirán conceptos de la teoría de autómatas
y de los lenguajes formales. También se estudiarán diferentes modelos de
máquinas computacionales, gramáticas y lenguajes formales.
Podemos clasificar los problemas en varios tipos:
Veremos qué es lo que se puede computar y qué es lo que no, hablaremos sobre los
recursos de tiempo y memoria. Determina la frontera entre lo que puede y no
puede hacer un computador (problema de la parada).
Dichos primeros posts servirán de base para luego ver cómo construir
Compiladores e Intérpretes.
11-01-2025
En este artículo de introducción a la Teoría de Autómatas y Lenguajes Formales, veremos los conceptos básicos y notación alfabetos, lenguajes, gramáticas y autómatas. La parte más importante de este campo es comprender la relación entre estos últimos tres conceptos.
11-01-2025
Autómata Finitos Determinitas, No Deterministas y No Deterministas de cadena vacía. Equivalencia entre varios tipos y minimización de autómatas.
12-01-2025
Definición de los lenguajes regulares y del álgebra expresiones regulares. Cómo construir autómatas finitos que aceptan expresiones regulares y cómo obtener la expresión regulare de un autómata. El lema del bombeo.
13-01-2025
Definición de una gramática y sus diferentes tipos. Derivaciones y los lenguajes que generan. Árboles sintácticos. Las diferentes formas normales de una gramática.
13-01-2025
Autómatas de Pila por vaciado de pila, estados finales o deterministas. Cómo pasar de APN a APF y viceversa. Equivalencia con gramáticas independientes del contexto. Lema del Bombeo para lenguajes independientes del contexto.
13-01-2025
Definición de una máquina de Turing y algunas de sus variaciones. Demostración de que dichas variaciones son equivalentes a la máquina de Turing estándar. Máquina de Turing Universal. Computación de funciones y la tesis de Church-Turing. Autómatas Linealmente Acotados.
14-01-2025
Lenguajes generados por las máquinas de Turing. Análisis de la complejidad de una máquina de Turing y las clases de complejidades P y NP. Decibilidad y el problema de la parada.
