Tecnologia

Universidad Fermín Toro
Facultad de Ingeniería
Escuela de Computación










Profesor:
Edecio Freite
Integrantes:
Miguel Uzcategui CI.- 16534910
Gustavo Brito CI.-16402784






Introducción

Los autómatas son mecanismos formales para las gramáticas y lenguajes. En 1936 Turing desarrollo lo que se puede llamarprimer autómata: la “máquina de Turing”. Podría visualizársele como un tocacintas sofisticado con una cinta arbitrariamente infinita. La cinta se marca en secciones de tal manera que en cada sección se puede almacenar un bit de información. La cabeza es un mecanismo que se mueve a través de la cinta con la capacidad de leer o escribir sobre está. Cuenta también con un mecanismo de control colocadoen la cabeza de la cinta, que informa qué acciones tomar dependiendo de la lectura de cada bit de información. Sus características y conducta de la máquina de Turing la calificaron como lo que se le llegó a conocer una Máquina de Estados Finitos (MEF), también se le podría concebir como un Autómata Finito (AF).Este artefacto es asombrosamente simple y asume que nuestro universo es granular; esdecir, que se mueve en pasos discretos de tiempo aun cuando éstos pudieran ser imaginados tan pequeños como se quisiera, incluso en miles de millonésimas de segundo. Durante cualquiera de esas instancias, un AF se encontraría en un cierto estado describible. La descripción podría ser extremadamente intrincada o sumamente simple; la única limitación consistía en que debería encontrarse necesariamentedentro de un conjunto finito de estados posibles (Esté número podrá ser muy elevado, pero no infinito).Entre el instante inicial y el siguiente paso de tiempo discreto, el AF, usando cualquier tipo de información sensorial que cualquier máquina particular pudiera tener disponible, tomaría nota del mundo externo. Acto seguido, refiriéndose a la 'tabla de reglas' que controla la conducta, el AFconsideraría tanto la información sensorial como su propio estado interno para determinar tanto la conducta que la máquina debería exhibir como el estado interno que debería asumir en ese instante







Accesibilidad entre estados
p ϵ Q es accesible desde q ϵ Q, pAq, si existe una palabra x ϵ ∑* tal que f’ (q, x) =p. A efectos de simplificar los autómatas, todos aquellos estados noaccesibles desde el inicial, se puede borrar, ya que no afectaran al comportamiento del autómata, al no poder nunca llegar a ellos.
Ejemplo: En el autómata A1 los dos estados son accesibles desde cualquiera. en el caso de que tuviera el autómata A´1 = ({0,1}, {q0,q1,q2}, f, q0, { q0,q2}), donde f define como:
f (q0, 0)= q0
f (q0, 1)= q1
f (q0, 0)= q1
f (q0, 1)= q0
f (q0, 0)= q2
f (q0, 1)=q1
0 0
q0 1 q1
1
q2 1
0
El estado q2 no sería accesible desde q0 ni q1, por lo que se puede eliminar sin afectar el comportamiento del autómata.






Autómata conexosUn AFD es conexo si para cada estado q ϵ Q, q es accesible desde q0.
Ejemplo: en el ejemplo anterior, A1 es conexo y A´1 no lo es.


Equivalencia de AFD
Al igual que en el caso de las maquinas secuenciales, se puede definir la equivalencia de autómatas finitos. Se representaran primero unas definiciones previas a la de la equivalencia entre autómatas finitos deterministas.Equivalencia entre estados
Dos estados p, q  Q son equivalentes pEq, si
x  ,  (p,x)  F  (q,x)  F
Si las transiciones de p con la entrada x llegan a un estado final, las transiciones de q con x también tienen que llegar, y si las transiciones de p con x no llegan a un estado final, las transiciones de q con x tampoco deben llegar. se puede demostrar fácilmente que para...