Automatas

ANTECEDENTES DE LA TEÓRIA DE AUTÓMATAS

Debido a ciertas etapas en los procesos de fabricación, se llegó a pensar en la posibilidad de dejar ciertas tareas tediosas, repetitivas peligrosas, se llegó a pensar en que no pudieran afectarle las condiciones ambientales adversas; así nació la máquina de automatización.

En 1969 Fordy general Motor impusieron a los proveedores de automatismos ,a medio camino entre los microcomputadores y la lógica cableada aparecen los primeros modelos autómatas limitados originalmente a tratamientos de lógica secuencial, los autómatas se desarrollaron rápidamente y actualmente extienden sus aplicaciones del conjunto de sistemas de control de procesos y de máquinas.

La teoría de autómatas “ es el estudio de las máquinas o dispositivos abstractoscon calidad de computación”.

En la década de la de 1930 antes de que existieran las computadoras Turing estudio una máquina abstracta que poseía la misma capacidad que los computadores de hoy en día.

En 1940 y 1950 otros investigadores estudiaron tipos de máquinas más sencillas hoy conocidas como “autómatas finitos “.

A finales de 1950 Chomsky comenzó el estudio de las gramáticasformales

En 1969 Cook extendió los estudios realizados por Turing acerca de lo que se puede computar y lo que no.

















CONCEPTOS BÁSICOS DE LA MATERIA

AUTÓMATA: Es un instrumento o herramienta que tiene varios estados en los cuales puede estar de acuerdo a ciertas condiciones.

ARBOL DE DERIVACIÓN: El árbol donde los nodos interiores se etiquetan con variables, ylas hojas se etiquetan con símbolos terminales , para cada hoja existe un nodo interno , debe existir una producción en la que la cabeza sea la etiqueta del nodo, y las etiquetas de sus hijos, leídas de izquierda a derecha forman parte del cuerpo de la producción.

PALABRA: Es la unión de dos o más caracteres sin necesidad de que estos tengan alguna validez por lo menos en el entorno detrabajo.

PALINDROMO: Se puede leer datos de todas las formas( izquierda-derecha,derecha-izquierda-arriba-abajo, etc):

RECERSIVO: Palabra que se puede leer desde el inicio o desde el final y suena igual.

CONCATENACIÓN: Unión de dos o más caracteres con un significado valido.

ALFABETO: Conjunto finito de caracteres

LENGUAJE: Conjunto de unidades finitas fundamentales que consta d reglasCERRADURA : Conjunto que inicia con cualquier carácter como {0,1,2,3}


CERRADURA DE KLEENE :Conjunto que inicia con un carácter nulo como
{ 0,1,2,3,4}



CARÁCTER: Es la representación más simple.

Por ejemplo:”a”,”A”

CARÁCTER NULO: Representa un espacio vacío.
Este tipo de carácter loencontramos gráficamente de }
distintas forma


ARBOL: Estructura jerárquica que consta de nodos donde del nodo raíz se derivan los siguientes nodos subsecuentes y ya sea que puedan ser nodos terminales o no terminales.

SÍMBOLO TERMINAL: Marca el final de un recorrido , en gramáticas regulares lo vamos a identificar como aquel carácter escrito en minúsculas


SÍMBOLO NOTERMINAL: Marca la secuencia de estados que continuan o finalizan dependiendo del recorrido y lo vamos a identificar por una letra mayúscula

UNION:


POTENCIACION:



INTERSECCIÓN:




VERICE:



HOJAS:



NODO:



ARBOL DE DERIVACIÓN:



CONJUNTO FINITO DE SÍMBOLOS:



EXPRESIÓN REGULAR:



AUTÓMATA DE MOORE:


AUTÓMATA DE MEALY:




GRAMATICA REGULAR:Es una cuádrupla de elementos (alfabeto, símbolos no terminales, tabulación , relación de entradas y salidas).


G=






































MÁQUINA DE TURING

En los años 30 de este siglo, Alan Turing formalizo el concepto de un algoritmo, con la presentación de un dispositivo computacional abstracto y caracterizó las...