Automatas Finitos, Caracteristicas y Prototipos

AUTÓMATAS FINITOS, CARACTERÍSTICAS Y PROTOTIPOS DE AUTÓMATAS

Hoy en día parece que no existe ningún límite a lo que un computador puede llegar a hacer, y da la impresión de que cada vez se puedenresolver nuevos y más difíciles problemas. El hombre ha tratado de buscar procedimientos y máquinas que le faciliten la realización de cálculos (aritméticos primero, y otros más complejosposteriormente). El avance tecnológico para representar datos y/o información por un lado, y el diseño de nuevas formas de manejarlos, propician el desarrollo de dispositivos y máquinas de calcular.

Además,un aspecto importante en el desarrollo de los computadores, es sin duda, su aplicación para resolver problemas científicos y empresariales. Esta aplicación hubiese resultado muy difícil sin lautilización de procedimientos que permiten resolver estos problemas mediante una sucesión de pasos claros, concretos y sencillos, es decir algoritmos. No obstante, el avance de la tecnología y de lasmatemáticas, y más en concreto de la teoría de conjuntos y de la lógica, permiten plantearse aspectos de la computación, siendo esta el propósito inicial de hacer precisa la noción intuitiva de funcióncalculable; esto es, una función cuyos valores pueden ser calculados de forma automática o efectiva mediante un algoritmo, y construir modelos teóricos para ello (de computación).

Al respecto convienedecir que, un autómata es una maquina abstracta que reconoce un programa, el cual toma una cadena y responde sí o no de acuerdo a si ésta es una frase del programa, esta cadena puede crearse en undiagrama de flujo el cual puede ser determinista o no determinista, y este último se caracteriza por que en un símbolo de entrada se puede dar el caso de tener más de una transición.

Ambos tipos deautómatas pueden convertirse en expresiones regulares, los autómatas finitos no deterministas (AFN) pueden ser representados mediante un grafo de transiciones, en el cual los nodos son los estados y...