Linea de tiempo historia y evolución de la teoría de autómatas y lenguajes formales
-
D.Hilbert
Durante el transcurso de un congreso internacional, formula varias preguntas sobre las matemáticas y el problema "Entscheidungsproblem" -
K.Godel
Formula el teorema de la incompletitud "todo sistema de primer orden consistente que contenga los teoremas de la aritmética y cuyo conjunto de axiomas sea recursivo no es completo" -
Church, Kleene, Turing y Post
los tres primeros mostraban problemas que eran efectivamente indecidibles; church y Turing probaron ademas que el Entscheidungsproblem era un problema indecidible.
Post formula un modelo de procedimiento efectivo a traves de los llamados sistemas deductivos formales. -
McCullon y Pitts
Describen los cálculos lógicos inmersos en un dispositivo que habían diseñado para simular la actividad de una neurona biológica. el dispositivo recibía o no, una serie de impulsos eléctricos por sus entradas que se ponderaban y producían una salida binaria. las salidas y entradas se podían considerar como cadenas de 0 y 1. la notación utilizada es la base para el desarrollo de expresiones regulares en la descripcion de conjuntos de cadena de caracteres -
C. Shannon
define los fundamentos de la teoría de la información, y utiliza esquemas para poder definir sistemas discretos, parecidos a los autómatas finitos, relacionándolos con cadenas de Markow, para realizar aproximaciones a los lenguajes naturales -
J. Von Neumann
Introduce el termino de teoría de autómatas y dice sobre los trabajos de McCulloch-Pitts " el resultado mas importante de McCulloch-Pitts es que cualquier funcionamiento en este sentido, que pueda ser definido en todo, lógicamente, estrictamente y sin ambigüedad, en un numero finito de palabras, puede ser realizado también por una tal red neuronal formal " -
Kleene
realiza un informe sobre los trabajos de McCulloch-Pitts que se publica en 1956. En este informe Kleene demuestra la equivalencia entre lo que el llama "dos formas de definir una misma cosa", que son los sucesos regulares ,es decir expresiones regulares, y sucesos especificados por un autómata finito -
D.A.Huffman
Utiliza conceptos como estados de un autómata y tabla de transiciones -
Princenton Univ. Press
Publica el libro Autómatas Studies. Editado por C.Shannon y J.mcCarthy ,donde se recoge una serie de trabajos sobre autómatas y lenguajes formales -
N. Chomosky
Propone tres modelos para la descripción de lenguajes, que son la base de su futura jerarquía de los tipos de lenguaje, que ayudo con los lenguajes de programación -
Rabin y Scott
obtienen un modelo de computador con una cantidad finita de memoria, al que llamaron autómata de estados finitos. demostraron que su comportamiento posible era básicamente el mismo que el descrito mediante expresiones regulares, desarrolladas a partir del trabajo de McCulloch y Pitts