Evolución de la teoría de autómatas y lenguajes formales

Evolución de la teoría de autómatas y lenguajes formales

1. 1. Comienza en el siglo XIX

   • Con los fundadores de la Lógica Simbólica
     • Gottlob Frege (1848 - 1925)
       • Sus obras reducen la aritmética a la lógica
         • Fundamentos de la aritmética, 1884. Leyes Basicas de la aritmética, 1893
           • Bertrand Rusell (1872 - 1970)
             • Descubre una paradoja en la teoría de conjuntos
               • con ayuda de Alfred North Whitehead (1861 - 1947)
                 • Idea teoría de tipos para evitar la paradoja
                 • Publica: Principios de las matematicas
             • Su obra se vino abajo con
               • Kurt Gödell (1906 - 1978)
                 • Dice: "Toda teoría matemática ha de ser incompleta, siempre hay afirmaciones que no se pueden comprobar"
           • Recibe apoyo de
             • David Hilbert (1862 - 1943)
               • Publica 23 problemas pendientes de solución
     • George Boole

2. 2. En 1937 nace la informática teórica

   • Alan Mathison Turing (1912 - 1953)
     • "Números Calculables" introdujo la maquina de Turing
       • Formalizo el concepto de Algoritmo
       • Precursora de las maquinas de calcular automáticas
     • Padre de la teoría de la computabilidad
       • Modelo de la computación actual

3. 3. En 1938, en la ingeniería eléctrica

   • Claude Elwood Shannon
     • aplica la lógica matemática para el análisis de circuitos
     • Crea teoría matemática de la comunicación
       • Aporta a las telecomunicaciones
     • Sus ideas dan origen a
       • Teoría de las maquinas secuenciales
       • Autómatas finitos
         • Mas sencillas que las de Turing
         • aplicadas en
           • Teoría de control, construcción de compiladores e intérpretes, lingüística, simulación del sistema nervioso
         • nacen:autómatas a pila, lineal acotados, generadores y transductor

4. 4. En la lingüística, 1950

   • Avram Noam Chomsky
     • Introduce: "Teoría de los lenguajes formales"
       • Herramientas que se aplican al lenguaje natural y de programación
         • 4 grados de relación entre maquinas y lenguajes formales
           • Tipo 0: lenguajes sin restricción, problemas computables
           • Tipo 1: con restricciones, autómatas lineales acotados
           • Tipo 2: Analizados con autómatas a pila
           • Tipo 3: Lenguajes regulares y autómatas finitos