TEORIA DE AUTOMATAS
Verano 2025
MCT. Luis Daniel Abella Reyes
TEORIA DE AUTOMATAS
Introducción a la Teoría de Autómatas
Semana 1
Introducción a la Teoría de Autómatas
Introducción a la Teoría de Autómatas
Antecedentes de la Teoría de Autómatas
La Teoría de Autómatas es una rama de la informática y de las matemáticas que
se centra en el estudio de los modelos matemáticos abstractos de sistemas
computacionales.
Esta materia se ha desarrollado gracias a
la confluencia de campos muy diferentes,
como son las matemáticas, la teoría de
máquinas, la linguistica, etc.
Entonces se puede considerar como
una materia multidisciplinaria.
En donde se estudia la relación que hay entre lenguaje, gramática y autómata y
sus posibles aplicaciones.
Introducción a la Teoría de Autómatas
Toda comunicación emplea:
Un lenguaje, que se puede definir como un conjunto de palabras o
cadenas formadas por símbolos de un alfabeto.
La gramática que define la estructura de los lenguajes queda la forma
válida en la que se pueden combinar los símbolos del alfabeto para
construir cadenas correctas.
Una máquina abstracta o autómata la cual es un dispositivo teórico que
recibe como entrada una cadena de símbolos y los procesa cambiando de
estado de tal manera que genera una determinada la salida.
Los autómatas sirven para determinar si una palabra pertenece o no a un
determinado lenguaje mientras que las gramáticas permiten definir lenguajes
y los autómatas podrán reconocer las palabras de dichos lenguajes.
Introducción a la Teoría de Autómatas
A pesar de la conexión que hay entre estos conceptos, los trabajos iniciales
sobre autómatas y lenguajes tienen sus orígenes en los años 30 las
matemáticas estaban dominados por temas como la lógica y los sistemas
axiomáticos.
A principio del siglo XX muchos matemáticos creían que era posible encontrar
un sistema axiomático único en el que podrían basarse todas las matemáticas,
mediante un conjunto de axiomas y reglas de inferencia de manera que las
podrían reducir las matemáticas a un sistema computacional con el cual
pudieran deducir la veracidad o falsedad de cualquier enunciado matemático.
En 1931 el austriaco Kurt Gödel publicó el teorema de la
incompletitud, en el que demostraba que era imposible la
completa axiomatización de las matemáticas.
Incrementando así el debate por el poder de los métodos
axiomáticos y los procesos computacionales.
Introducción a la Teoría de Autómatas
En 1937 el matemático inglés Alan Turing publicó en su artículo
“Sobre los números computables” la conocida Máquina de
Turing, una entidad matemática abstracta, con la que formalizó
el concepto de algoritmo además de que demostró que
muchos los problemas perfectamente definidos no pueden ser
resueltos mediante una Máquina de Turing, es decir, que no
son computables, ratificando la teoría de Gödel.
Por otro lado, el matemático Claude Shannon estableció las bases para la
aplicación de la lógica matemática al diseño de los circuitos combinatorios y
secuenciales.
Las ideas de Shannon derivarían en la formalización de una
teoría de máquinas secuenciales y autómatas que permitirían
representar formalmente el comportamiento de un dispositivo
electrónico o mecánico.
Introducción a la Teoría de Autómatas
Los autómatas son sistemas que aceptan señales del medio que los rodea
cambian de estado como consecuencia de estas señales y transmiten otras
señales de regreso.
A finales de los años 50 se empezó a estudiar la utilidad de los autómatas en
relación con los lenguajes de programación y su proceso de traducción.
También en la década de los años 50, en lingüista y pensador
Noam Chomsky, en un intento de formalizar los lenguajes
naturales estableció las bases de la lingüística matemática o
formal y con ello proporcionó una poderosa herramienta que
facilitó los primeros lenguajes de programación de la época
Introducción a la Teoría de Autómatas
¿Por qué Estudiar Teoría de Autómatas?
La Teoría de Autómatas es una rama de la informática y de las matemáticas que
se centra en el estudio de los modelos matemáticos abstractos de sistemas
computacionales.
Según la Education Activities Board of IEEE con respecto al estudio de las
Ciencias Computacionales:
“A pesar de la enorme amplitud de la informática,
existen conceptos y habilidades que son comunes
a la informática en su conjunto”.
“Todos los estudiantes de informática tienen que
aprender a integrar la teoría y la práctica, a
reconocer la importancia de la fracción para
apreciar el valor de un buen diseño de ingeniería”.
Introducción a la Teoría de Autómatas
¿Por qué Estudiar Teoría de Autómatas?
Ciencias de la Computación: Cuerpo de conocimiento que se ocupa del estudio
de los fundamentos teóricos de la información y la computación y de su
implementación y aplicación de los sistemas computacionales.
Gibbs y Tucker mencionan en su artículo “A model curriculum
for a Liberal arts degree in computer science” (1986):
“No se debe entender que el objetivo de las ciencias de la
computación sea la construcción de programas sino el
estudio sistemático de los algoritmos y estructuras de
datos, específicamente de sus propiedades formales”.
Introducción a la Teoría de Autómatas
¿Por qué Estudiar Teoría de Autómatas?
Las propiedades matemáticas fundamentales de software hardware y las
aplicaciones de los mismos buscan responder a preguntas como:
¿Cómo puede construirse un programa para resolver un problema.?
¿El programa realmente resuelve el problema?
¿Cuánto se tarda el programa en realizar un cómputo? (Complejidad
temporal).
¿Cuánta memoria se necesita para realizar el cómputo? (Complejidad
espacial)
¿Qué paradigma de computación emplea? (Imperativo, POO,
programación lógica, etc.)
¿Qué se puede computar y qué no se puede computar?.
Introducción a la Teoría de Autómatas
¿Por qué Estudiar Teoría de Autómatas?
Aplicaciones directas de conceptos propios de la Ciencia de Computación.
Videojuegos
Comportamiento de personajes.
Compiladores y procesamiento de lenguaje natural.
Análisis léxico de lenguajes de programación.
Búsqueda de cadenas o comparación de patrones.
Diseño de nuevos lenguajes de programación o ampliación.
Implementación de protocolos robustos.
Para clientes o usuarios.
Sistemas de seguridad.
Criptografía Moderna y sus protocolos.
Introducción a la Teoría de Autómatas
¿Por qué Estudiar Teoría de Autómatas?
La construcción de sistemas computacionales más elegantes y sencillos.
Diseño de máquinas secuenciales y Código.
Diseño de estructuras.
Búsqueda de cadenas y comparación de patrones.
Software para enseñar y evaluar circuitos digitales.
Escanea grandes cantidades de textos.
Software para verificar sistemas que tienen un número finito de estados.
Etcétera.
Introducción a la Teoría de Autómatas
La Teoría de Autómatas y su relación con otras áreas
Introducción a la Teoría de Autómatas
Pilares de la Teoría de Autómatas
Los tres pilares que sustentan a la Teoría de Autómatas son:
Introducción a la Teoría de Autómatas
Pilares de la Teoría de Autómatas
Los tres pilares que sustentan a la Teoría de Autómatas son:
Introducción a la Teoría de Autómatas
Pilares de la Teoría de Autómatas
¿Preguntas?
MCT. Luis Daniel Abella Reyes
