Automatas Finitos

June 17, 2015 | Views: 1350

Begin Learning Cyber Security for FREE Now!

FREE REGISTRATIONAlready a Member Login Here

Contribution Credit: @kierc117

 

Automata Finito
Un automata finito es un vector de 3 elementos
M=(I,S,DELTA,F)
donde I es el conjunto finito de entradas (no vacio), S es el conjunto finito de estados, DELTA es la funcion de transicion de estados y F es el conjunto finito de estados finales (incluidos en S)

el hecho de que todos los conjuntos sean finitos le otortga a este elemento el atributo de finito. Tambien se puede desprender de la definicion que un automata finito es un tipo especial de maquina secuencial , en la cual no existen señales de salida como tal si no que solo hay señales de entrada y estado

un automata finito es un conjunto de estados y un control que se mueve de un estado a otro en respuesta a entradas externas
es un modelo matematico de un sistema que recibe una cadena constituida por simbolos de un alfabeto y determinado

Clasificacion
-Determinista: cada combinacion (estado, simbolo de entrada) produce un solo estado

-no determinista: cada combinacion (estado, simbolo de entrada) produce varios estados y ademas son posibles las transiciones con landa

Automata determinista
es un automata finito determinista es una quintupla (Q, sigma, delta, 90, F) donde

Q= es un conjunto finito no vacio de estados
sigma = Alfabeto de entrada
delta= QxSigma -> Q, funcion de transicion que especifica a que estado pasa el automata desde el estado actual al recibir un simbolo de entrada. esta funcion se define para todas las parejas posibles de estados y de simbolos de entrada . delta(9,9) = 9′
significa que del estado “9” con el simbolo “9”, el automata para al estado 9′
90 pertenece Q : estado inicial de automata
FQ : conjunto de estados finales

Representacion
tablas
-es una represntacion clasica de una funcion con 2 argimentos
-en las filas se colocaran los estados y en las columnas los simbolos del alfabeto de entrada
-cada interseccion fila (estado9) columna (caractera) corresponde al estado F(9,a)
-Estado inicial se representa con ->
-los estados finales con un *

Diagramas de transicion
– Es un grafo en el que los vertices representando los distintos estados y los arcos las transacciones entre los estados
-cada arco va etiquetado con el simbolo que corresponde a dicha transicion
-El estado inicial se preresenta con ->
-los estados finales con un doble circulo

Share with Friends
FacebookTwitterLinkedInEmail
Use Cybytes and
Tip the Author!
Join
Share with Friends
FacebookTwitterLinkedInEmail
Ready to share your knowledge and expertise?
2 Comments
  1. Good read! I hope to see more

  2. Nice Writeup!

Comment on This

You must be logged in to post a comment.

Our Revolution

We believe Cyber Security training should be free, for everyone, FOREVER. Everyone, everywhere, deserves the OPPORTUNITY to learn, begin and grow a career in this fascinating field. Therefore, Cybrary is a free community where people, companies and training come together to give everyone the ability to collaborate in an open source way that is revolutionizing the cyber security educational experience.

Support Cybrary

Donate Here to Get This Month's Donor Badge

 

We recommend always using caution when following any link

Are you sure you want to continue?

Continue
Cancel