Descubre AUTÓMATAS y LENGUAJES

Tabla de Contenidos

Lenguajes y Autómatas

Lenguajes y Autómatas

El desarrollo de los ordenadores en la década de los 40, con la introducción de los programas en la memoria principal, y posteriormente con los lenguajes de programación de alto nivel, propician la distinción entre lenguajes formales, con reglas sintácticas y semánticas rígidas, concretas y bien definidas, de los lenguajes naturales como el inglés, donde la sintaxis y la semántica no se pueden controlar fácilmente. Los intentos de formalizar los lenguajes naturales, llevan a la construcción de gramáticas, como una forma de describir estos lenguajes, utilizando para ello reglas de producción para construir las frases del lenguaje. Se puede entonces caracterizar un Lenguaje, mediante las reglas de una gramática adecuada.

Los trabajos de McCulloch y Pitts (1943) describen los cálculos lógicos inmersos en un dispositivo (neurona artificial) 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ía una salida binaria (existe pulso eléctrico o no). Las entradas y salidas se podían considerar como cadenas de 0 y 1, indicando entonces la forma de combinar la cadena de entrada para producir la salida. La notación utilizada es la base para el desarrollo de expresiones regulares en la descripción de conjuntos de cadenas de caracteres.

C. Shannon (1948) 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 Markov, para realizar aproximaciones a los lenguajes naturales.

automatas y lenguajes 1

J. Von Neumann (1948) introduce el término de teoría de autómatas, y dice sobre los trabajos de McCulloch-Pitts: ... el resultado más 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 número finito de palabras, puede ser realizado también por una tal red neuronal formal.

La necesidad de traducir los algoritmos escritos en lenguajes de alto nivel al lenguaje máquina, propicia la utilización de máquinas como los autómatas de estados finitos, para reconocer si una cadena determinada pertenece (es una frase de) a un lenguaje concreto, usando para ello la función de transición de estados, mediante un diagrama de transición o una tabla adecuada. Tenemos así otra forma de caracterizar los lenguajes, de acuerdo con máquinas automáticas que permitan reconocer sus frases.

S.C. Kleene, en 1951, realiza un informe (solicitado por la RAND Corporation) sobre los trabajos de McCulloch-Pitts, que se publica en 1956. En este informe, Kleene demuestra la equivalencia entre lo que él llama "dos formas de definir una misma cosa", que son los sucesos regulares (que se pueden describir a partir de sucesos bases y los operadores unión, concatenación e iteración (*) ), es decir, expresiones regulares, y sucesos especificados por un autómata finito.

automatas y lenguajes 2

Rabin y Scott (1960) 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 de los trabajos de McCulloch y Pitts. No obstante lo dicho, 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 desarrollo de máquinas reconocedoras de otros tipos de lenguajes y de las gramáticas correspondientes, asociadas a los mismos.
En 1956, la Princenton Univ. Press publica el libro Automata Studies, editado por C. Shannon y J. McCarthy, donde se recogen una serie de trabajos sobre autómatas y lenguajes formales.

D. A. Huffman (1954) ya utiliza conceptos como estado de un autómata y tabla de transiciones.

N. Chomsky (1956) propone tres modelos para la descripción de lenguajes, que son la base de su futura jerarquía de los tipos de lenguajes, que ayudó también en el desarrollo de los lenguajes de programación. Para ello intentó utilizar autómatas para extraer estructuras sintácticas (....el inglés no es un lenguaje de estados finitos.) y dirige sus estudios a las gramáticas, indicando que la diferencia esencial entre autómatas y gramáticas es que la lógica asociada a los autómatas (p.e., para ver la equivalencia entre dos de ellos) es Decidible, mientras que la asociada a las gramáticas no lo es. Desarrolla el concepto de gramática libre del contexto, en el transcurso de sus investigaciones sobre la sintaxis de los lenguajes naturales.

automatas y lenguajes 3

Backus y Naur desarrollaron una notación formal para describir la sintaxis de algunos lenguajes de programación, que básicamente se sigue utilizando todavía, y que podía considerarse equivalente a las gramáticas libres del contexto.
Consideramos entonces los lenguajes libres (independientes) del contexto, y las gramáticas libres del contexto y los autómatas con pila, como forma de caracterizarlos y manejarlos. Los distintos lenguajes formales que se pueden construir sobre un alfabeto concreto pueden clasificarse en clases cada vez más amplias que incluyen como subconjunto a las anteriores, de acuerdo con la jerarquía establecida por Chomsky en los años 50.

Se puede llegar así, de una forma casi natural a considerar las máquinas de Turing, establecidas casi 20 años antes, como máquinas reconocedoras de los lenguajes formales dependientes del contexto o estructurados por frases, e incluso a interpretar la Tesis de Turing como que un sistema computacional nunca podrá efectuar un análisis sintáctico de aquellos lenguajes que están por encima de los lenguajes estructurados por frases, según la jerarquía de Chomsky".

En consecuencia, podemos utilizar la teoría de autómatas y los conceptos relativos a gramáticas sobre distintos tipos de lenguajes, para decidir (si se puede) si una función (o problema) es calculable, en base a que podamos construir un algoritmo solución mediante un lenguaje que puede ser analizado mediante alguna máquina de las citadas anteriormente.

automatas y lenguajes 4

Los temas sobre autómatas, computabilidad, e incluso la complejidad algorítmica fueron incorporándose a los currículos de ciencias de la computación de diferentes universidades, mediada la década de los 60. Esta incorporación puso de manifiesto que las ciencias de la computación habían usado gran cantidad de ideas de muy diferentes campos para su desarrollo, y que la investigación sobre aspectos básicos podía cooperar y aumentar los avances de la computación.