MODELOS FORMALES DE COMPUTACION: AUTOMATAS Y MAQUINAS

Automatismos

• Introducción. Definición de automatismo.

La automatización de una máquina o proceso productivo simple tiene como consecuencia la liberación física y mental del hombre de dicha labor. Entendemos por «automatismo» el dispositivo físico (ya sea eléctrico, neumático electrónico, etc.) que realiza esta función controlando su funcionamiento.

• Principio de un sistema automático.

Todo sistema automático por simple que sea se basa en el esquema representado en la siguiente figura:
Señales de detección
Automatismo Captadores o parte de Máquina o proceso
Trabajo control operativo
Actuadores

Este circuito cerrado es lo que se conoce como bucle o lazo.

Autómatas programables

• Introducción. Definición de autómata programable.

Entendemos por Autómata Programable, o PLC (Controlador Lógico Programable), toda máquina electrónica, diseñada para controlar en tiempo real y en medio industrial procesos secuenciales. Su manejo y programación puede ser realizada por personal eléctrico o electrónico sin conocimientos informáticos. Realiza funciones lógicas: series, paralelos, temporizaciones, contajes y otras más potentes como cálculos, regulaciones, etc.
Otra definición de autómata programable sería una «caja» en la que existen, por una parte, unos terminales de entrada (o captadores) a los que se conectan pulsadores, finales de carrera, fotocélulas, detectores...; y por otra, unos terminales de salida (o actuadores) a los que se conectarán bobinas de contactores, electroválvulas, lámparas..., de forma que la actuación de estos últimos está en función de las señales de entrada que estén activadas en cada momento, según el programa almacenado.
La función básica de los autómatas programables es la de reducir el trabajo del usuario a realizar el programa, es decir, la relación entre las señales de entrada que se tienen que cumplir para activar cada salida, puesto que los elementos tradicionales (como relés auxiliares, de enclavamiento, temporizadores, contadores...) son internos.

Estructura de un autómata programable. 
La estructura básica de un autómata programable es la siguiente:

•  AUTOMATA FINITO DETERMINISTA***

Un Autómata Finito Determinista consiste en un dispositivo que puede estar en cualquier estado entre un número finito, uno de los cuales es el estado inicial y por lo menos uno es un estado de aceptación.

A este dispositivo está unido un flujo de entrada por medio del cual llegan en secuencia los símbolos de un alfabeto determinado.

La máquina tiene capacidad para detectar los símbolos conforme llegan y, basándose en el estado actual y el símbolo recibido, ejecutar una transición consistente en cambiar a otro estado o la permanencia en el mismo.

El programa de un Autómata Finito Determinista no debe contener ambigüedades (para un estado un determinado símbolo sólo puede producir una determinada acción).

Se dice que un Autómata Finito Determinista acepta su cadena de entrada si, después de comenzar sus cálculos en el estado inicial la máquina cambia a un estado de aceptación después de leer el último símbolo de la cadena.

Si después de leer el último símbolo no queda en estado de aceptación, se dice que la cadena ha sido rechazada. Si la entrada es una cadena vacía (l) será aceptada si y sólo si el estado inicial es también un estado de aceptación.

Un Autómata Finito Determinista consiste en una quíntupla ( S, S, d, i, F) donde:

• S, es un conjunto finito de estados. • S, es el alfabeto de la máquina. • d, es una función (función de transición) de S× S a S. • i, (un elemento de S) es el estado inicial. • F (un subconjunto de S) es el conjunto de estados de aceptación.

La interpretación de la función de transición d de un autómata finito determinista es que d(p,x)=q sí y sólo sí la máquina puede pasar de un estado p a un estado q al leer el símbolo x.

El diagrama de transición determinista sólo debe tener un arco que sale de un estado para cada símbolo del alfabeto. Además, dicho diagrama está completamente definido, es decir, debe existir un arco para cada símbolo del alfabeto.

• AUTOMATA FINITO NO DETERMINISTA***

Esta maquina se parece mucho a un AFD, pues también analiza cadenas construidas a partir de un S y solo puede tener un numero finito de estados, algunos de los cuales son de aceptación y uno es el estado inicial.

A diferencia de los AFD, la transición que se ejecuta en una etapa dada de un AFN puede ser incierta, es posible aplicar cero, una o mas de una transición mediante el mismo símbolo de entrada, como sucede con una maquina que no esta completamente definida.

Un AFN acepta una cadena si es posible que su análisis deje a la maquina en un estado de aceptación.

De manera formal, un AFN se define como sigue, un AFN consiste en una quíntupla (S,∑ , p, i, F) donde:

• S es un conjunto finito de estados. • ∑ es el alfabeto de la maquina • p es un sub-conjunto de SXS XS llamada relación de transiciones. • i es le estado inicial (un elemento de S) • F es la colección de estados de aceptación (un sub-conjunto de S). 

Maquinas turing

• Es una coleccion de celdas que se extiende infinitamente en ambas direcciones, es una cinta infinita.

• Cada celda es capaz de almacenar un unico simbolo.

• No existe una celda primera, ni una ultima y por lo tanto tiene capacidad de almacenamiento infinito.

• Los contenidos de las celdas pueden ser accedidos en cualquier orden.

• Existe una cabeza de lectura/escrita que puede moverse sobre la cinta y cada movimiento leera o escriba un simbolo.

Un movimento de la maquina turing
Un moviento de la TM se considerara el simbolo actual sobre la cabeza de lectura/escritura y el esta actual de la misma y la dinamica sera la siguiente:

1. Cambia de estado
2. Escribe un simbolo sobre la cinta, reemplazando el que existia previamente
3. Mueve la cabeza de lectura/escritura una celda a la izquierda o la derecha.

- Bibliografia
http://html.rincondelvago.com/automatas-programables_2.html
http://www.mitecnologico.com/Main/AutomatasFinitosDeterministicosYNoDeterministicos
http://www.slideshare.net/iscrquinter/parte-4-mquinas-de-turing