Autómatas y lenguajes formales

Un autómata es un modelo computacional consistente en un conjunto de estados bien definidos, un estado inicial, un alfabeto de entrada y una función de transición. Este concepto es equivalente a otros como autómata finito o máquina de estados finitos.

En un autómata, un estado es la representación de su condición en un instante dado. El autómata comienza en el estado inicial con un conjunto de símbolos; su paso de un estado a otro se efectúa a través de la función de transición, la cual, partiendo del estado actual y un conjunto de símbolos de entrada, lo lleva al nuevo estado correspondiente.

Históricamente, los autómatas han existido desde la Antigüedad, pero en el siglo XVII, cuando en Europa existía gran pasión por la técnica, se perfeccionaron las cajas de música compuestas por cilindros con púas, que fueron inspiradas por los pájaros autómatas que había en Bizancio y que podían cantar y silbar.

Así, a principios del siglo XVIII, el ebanista Roentgen y Kintzling mostraron a Luis XVI un autómata con figura humana llamado “La tañedora de salterio”. Por su parte, la aristocracia se apasionaba por los muñecos mecánicos de encaje, los cuadros con movimiento y otros personajes.

Los inventores más célebres son Pierre Jacquet Droz, autor de “El dibujante” y “Los músicos”, y Jacques Vaucanson, autor de “El pato con aparato digestivo”, un autómata que aleteaba, parloteaba, tragaba grano y evacuaba los residuos. Este último autor quiso pasar de lo banal a lo útil y sus trabajos culminaron en el telar de Joseph Marie Jaquard y la máquina de Jean Falcon dirigida por tarjetas perforadas.

El autómata más conocido en el mundo es el denominado “Máquina de Turing”, elaborado por el matemático inglés Alan Mathison Turing.

En términos estrictos, actualmente se puede decir que un termostato es un autómata, puesto que regula la potencia de calefacción de un aparato (salida) en función de la temperatura ambiente (dato de entrada), pasando de un estado térmico a otro. Un ejemplo más de autómata en la vida cotidiana es un elevador, ya que es capaz de memorizar las diferentes llamadas de cada piso y optimizar sus ascensos y descensos.

Fuente: Apunte Análisis, diseño e implantación de algoritmos de la facultad de contaduría y administración, UNAM

Publicado en Programación

Suscríbete:

who's online