Teocomp

UNIVERSIDAD NACIONAL DE TRUJILLO
FACULTAD DE CIENCIAS FISICAS Y MATEMÁTICAS
ESCUELA DE INGENIERIA INFORMÁTICA
AUTOMATAS FINITOS
TEORIA DE LA COMPUTACIÓN - III CICLO - 2013
INTEGRANTES:
LARCO BUCHELLI, VICTOR RAFAEL CONSTANTE JAVIER
ESQUIVEL GUEVARA, MARIA DEL CARMEN
LIMAY OLIVA, MARY LAURA CAROLINA
LUNAVICTORIA LOZANO, JUNIOR ELADIO

Trujillo, 16 de mayo del 2013RESUMEN
En el presente informe mostraremos y detallaremos el tema de “Automatas Finitos”, para lo cual definiremos conceptos importantes y relevantes, los cuales nos servirán para entender de manera rápida el tema en general. Por esa sencilla razón seremos muy breves explicando cada concepto, para no concentrarnos en la teoría, por el contrario queremos que este informe sea muy concreto yentendible. Mostraremos las principales definiciones, para luego proceder a profundizar ligeramente.
Veremos algunos ejemplos sencillos, que serán de mucha ayuda en la comprensión del tema principal. Al finalizar podremos ver una aplicación general de todos los conceptos dados.







INTRODUCCIÓN


































AUTOMATAS FINITOS
Todo procesoque recibe una o varias entradas, que las transforma y que después emite una salida recibe el nombre de SISTEMA.
Un sistema complejo por ejemplo sería el comportamiento del ser humano, el cual recibe infinidad de información de varios lados que se procesa de acuerdo con su estructura cognitiva y que en función de esto toma una decisión de lo que debe hacer. Su comportamiento o reacción a lainformación proporcionada no se puede determinar con exactitud, ya que depende además de la información de entrada, del entorno socioeconómico, edad valores, entre otros. Este tipo de sistemas recibe el nombre de sistemas infinitos.
Los autómatas finitos también reciben como entrada información que procesan y en función de ello emiten una salida. Un autómata finito recibe una palabra, la cual debeprocesar por medio de un recorrido a través de los diferentes estados que integran el autómata, y si al final del procesamiento de ésta el recorrido termina en un estado o posición de aceptación, se dice que la palabra forma parte el lenguaje
Un autómata es un sistema finito y por eso se le llama autómata, en donde si es posible determinar con exactitud la salida que se tendrá con ciertainformación.
Autómatas Finitos
Los Autómatas Finitos constan de cinco elementos fundamentales AF={∑, E, F, s,δ}. Un alfabeto {∑ un conjunto de estados finales (F) y una función,
δ: E x ∑  E que permite determinar cuál es el estado siguiente.
Las expresiones regulares se pueden representar por medio de autómatas finitos, a su vez los autómatas finitos pueden expresarse en forma gráfica por medio deun diagrama de transición o bien por medio de una tabla que recibe el nombre de tabla de transición.
Diagrama de transición
En los diagramas de transición, los estados se representan por medio de un circulo con el nombre del estado dentro de él. Los estados de aceptación o finales se distinguen porque tiene doble círculo, las transiciones se representan por aristas y se etiquetan con un símbolodel alfabeto. El estado inicial se distingue porque se hace incidir sobre él una flecha.



Tabla de transición
La información de un autómata, así como los valores que puede tomar la función δ, también se puede representar por medio de una tabla de transición.
AUTÓMATAS FINITOS DETERMINISTAS
Un autómata finito determinista es una quíntupla que denotaremos de manera genérica porM=(Q,Σ,q0,δ,F) donde:
Q es un conjunto finito cuyos elementos llamaremos estados.
Σ es un alfabeto que llamamos alfabeto de entrada.
q0∈Q es un estado señalado que llamamos estado inicial.
F es un subconjunto de Q no vacío, cuyos elementos llamamos estados finales.
δ es una aplicación de Q×Σ→Q , que llamamos función de transición.
La función de transición es la verdadera clave de la máquina....