Page 17 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

17

MÁQUINAS SECUENCIALES Y AUTÓMATAS FINITOS

La teoría de autómatas, que engloba también al estudio de las máquinas secuenciales, de hecho,
las máquinas secuenciales son un tipo de autómata, tiene su origen en el campo de la ingeniería
eléctrica. El matemático norteamericano Shannon (que luego se haría famoso por su teoría de la
información) vino a establecer las bases para la aplicación de la lógica matemática a los circuitos
combinatorios y posteriormente Hoffman en 1954 los amplió a circuitos secuenciales y utiliza
conceptos como estado de un autómata y tabla de transición. A lo largo de las décadas siguientes,
las ideas de Shannon se desarrollaron considerablemente, dando lugar a la formalización de una
teoría de las maquinas secuenciales y de los autómatas finitos (1956). Otros trabajos importantes
sobre máquinas secuenciales son debidos a Mealy (1955) y Moore.

Desde un frente totalmente distinto, el concepto de autómata finito aparece en 1943 con el artículo
de Mcculloch y Pitts titulado: “A Logical Calculus of the Ideas Immanet in Nervous Activity”,
donde describen los cálculos lógicos inmersos en un dispositivo (neurona artificial) que habían
ideado para simular la actividad de una neurona biológica. A partir de entonces, se han
desarrollado asociaciones de neuronas para constituir redes. Podemos considerar una RNA (red
neural artificial) como una colección de procesadores elementales (neuronas), conectadas a otras
neuronas o entradas externas, y con una salida que permite propagar las señales por múltiples
caminos. Cada procesador pondera las entradas que recibe y estos pesos pueden ser modificados
en aras de conseguir el objetivo previsto. Es lo que llamaremos función de aprendizaje.

Es decir, una RNA puede “aprender” de sus propios errores, por un proceso inductivo a partir de
un conjunto de ejemplos de lo que queremos aprender, frente al proceso deductivo, propio de los
sistemas expertos. Las características que hacen interesantes a las RNAs son su capacidad para
aprender (reproducir un sistema o función a partir de ejemplos), memorizar (almacenar un
conjunto de patrones o ejemplos), generalizar y abstraer (que permita recuperaciones a partir de
entradas defectuosas o incompletas). Las redes neuronales, dentro del perfil de teoría de la
computación, aportan paradigmas interesantes como son el cálculo paralelo, el aprendizaje
inductivo y su capacidad para realizar cálculos aproximados por medio de interpolación.

En el verano de 1951 Kleene fue invitado por el Rand Corporation para realizar un informe sobre
los trabajos de Mcculloch-Pitts. En este informe Kleene demuestra la equivalencia entre lo que la
llama “dos formas de definir una misma cosa”: los conjuntos regulares, los cuales pueden ser
descritos a partir de sucesos bases y los operadores unión, concatenación y clausura, es decir,
mediante expresiones regulares y los lenguajes reconocidos por un autómata finito.

Los autómatas finitos son capaces de reconocer solamente un determinado tipo de lenguajes,
llamados lenguajes regulares, que también se caracterizan mediante un tipo de gramáticas
llamadas así mismo-regulares. Esto lo abordaremos después……cuando se den los diferentes
tipos de lenguajes y la asociación con un tipo de autómata definido.

Una forma adicional de caracterizar este tipo de lenguajes es mediante las citadas expresiones
regulares, construidas mediante operadores sobre el alfabeto del lenguaje y otras expresiones
regulares, incluyendo el lenguaje vacío. Es fácilmente comprobable que, para un alfabeto
concreto, no todos los lenguajes que se pueden construir son regulares. Ni siquiera todos los
interesantes desde el punto de vista de la construcción de algoritmos para resolver problemas.
Hay entonces muchos problemas que no son calculables con estos lenguajes. Esto pone de
manifiesto las limitaciones de los autómatas finitos y las gramáticas regulares, y propicia el