Automatas

Michelle Brenes

El autómata es un ordenador analógico. Se trata de dispositivo electrónico o hidráulico diseñado para manipular la entrada de datos en términos de, por ejemplo, niveles de tensión o presiones hidráulicas, en lugar de hacerlo como datos numéricos. El dispositivo de cálculo analógico más sencillo es la regla de cálculo, que utiliza longitudes de escalas especialmente calibradas para facilitar la multiplicación, la división y otras funciones.

En Electrónica

• un sistema secuencial, aunque en ocasiones la palabra es utilizada también para referirse a un robot.

• . Puede definirse como un equipo electrónico programable en lenguaje no informático y diseñado para controlar, en tiempo real y en ambiente industrial, procesos secuenciales.

tipos de autómatas que reconocen tipos diferentes de lenguajes:

• Autómatas finitos• Autómatas a pila• Máquinas de Turing pila

Autómatas Finitos

Autómatas de Pila

Máquina de Turing

Aplicaciones

La disminución de tamaño y el

menor costo han permitido que

los autómatas sean utilizados

en todos los sectores de la

industria

Como…

Automóvil

Plantas químicas y petroquímicas

Metalurgia

Alimentación

Producción de energía

Tráfico

Fabricación de Neumáticos

Autómata FinitoEs aquel en cual para cada par (estado, símbolo) está perfectamente definido el siguiente estado al cual pasará el autómata, es decir para cualquier estado q en que se encuentre el autómata y con cualquier símbolo s del alfabeto leído, existe exactamente una transición que parte de q y está etiquetada con s. Formalmente, un autómata finito determinista (AFD) es similar a un Autómata de estados finitos, representado con una 5-tupla (S,Σ,T,s,A) donde:Σ es un alfabeto; S un conjunto de estados; T es la función de transición: ; es el estado inicial; es un conjunto de estados de aceptación o finales. Al contrario de la definición de autómata finito, este es un caso particular donde no se permiten transiciones vacías, el dominio de la función T es S (con lo cual no se permiten transiciones desde un estado de un mismo símbolo a varios estados).

AFND

Un autómata finito no determinista es aquel que presenta cero, una o más transiciones por el mismo carácter del alfabeto.Un autómata finito no determinista también puede o no tener más de un nodo inicial.Los AFND también se representan formalmente como tuplas de 5 elementos (S,Σ,T,s,A). La única diferencia respecto al AFD es T.AFD: AFND: (partes de S)Debido a que la función de transición lleva a un conjunto de estados, el automáta puede estar en varios estados a la vez (o en ninguno si se trata del conjunto vacío de estados).

AFND

Un autómata finito no determinista con transiciones ε permite cambiar de estado sin procesar ningún símbolo de entrada. Cuando el autómata llega a un estado, se encuentra en ese estado y en los estados a los que apunte éste mediante una transición ε.Un automata es un AFND: (partes de S)AFND-ε: (partes de S)Cuando el símbolo de entrada es la palabra vacía (ε), existe una transición ε entre los estados.

Automatas a Pila

Es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce. El lenguaje que reconoce un autómata a pila pertenece al grupo de los lenguajes de contexto libre en la clasificación de la Jerarquía de Chomsky.

Maquina de Turing

• La máquina de Turing es un modelo matemático abstracto que formaliza el concepto de algoritmo

• La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:

• avanzar el cabezal lector/escritor hacia la derecha. • avanzar el cabezal lector/escritor hacia la izquierda. • El cómputo es determinado a partir de una tabla de estados de la forma:• (estado, valor) (nuevo estado, nuevo valor, dirección)• Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la

cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a ser escrito en la cinta.

• Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.

• Mediante este modelo teórico y el análisis de complejidad de algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones en tiempo polinómico son encontradas según el determinismo y no determinismo respectivamente de la máquina de Turing.