Maquinas Finitas

Mérida, Yucatán a 05 de Febrero de 2013.

Ingeniería en Desarrollo de Software Área Aplicaciones de Cómputo en la Nube

Asignatura: Teoría de las Matemáticas de la Programación

Trabajo: Máquinas Finitas: Conceptos Elementales.

Profesor:M.G.T.I. Oscar Josué Uh Pérez

Alumnos: Luis Alberto Flores Novelo

Cuatrimestre y Grupo: 8-B

Matricula: 12090032c
Introducción
El origen de losautómatas finitos probablemente se remonta a su uso implícito en máquinas electromecánicas, desde principios del siglo XX. Ya en 1907, el matemático ruso Andréi Márkov formalizó un proceso llamado cadena de Markov, donde la ocurrencia de cada evento depende con una cierta probabilidad del evento anterior. Esta capacidad de "recordar" es utilizada posteriormente por los autómatas finitos, queposeen una memoria primitiva similar, en que la activación de un estado también depende del estado anterior, así como del símbolo o palabra presente en la función de transición.
Posteriormente, en 1943, surge una primera aproximación formal de los autómatas finitos con el modelo neuronal de McCulloch-Pitts. Durante la década de 1950 prolifera su estudio, frecuentemente llamándoseles máquinas desecuencia; se establecen muchas de sus propiedades básicas, incluyendo su interpretación como lenguajes regulares y su equivalencia con las expresiones regulares. Al final de esta década, en 1959, surge el concepto de autómata finito no determinista en manos de los informáticos teóricos Michael O. Rabin y Dana Scott.
En la década de 1960 se establece su conexión con las series de potencias y lossistemas de sobre escritura. Finalmente, con el desarrollo del sistema operativo Unix en la década de 1970, los autómatas finitos encuentran su nicho en el uso masivo de expresiones regulares para fines prácticos, específicamente en el diseño de analizadores léxicos (comando lex) y la búsqueda y reemplazo de texto (comandos ed y grep). A partir de ese tiempo, los autómatas finitos también se comienzana utilizar en sistemas dinámicos.
En fin las maquinas finitas son sumamente importante hoy en día, ya que nos permite usarlo en un sinfín de actividades cotidianas y diseñar casi todo tipo de máquinas.

Autómata Finito (Máquina Finita)
Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir unasalida.
Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerseen un estado final o de aceptación, que representa la salida.
La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.
El modelo neuronal de McCulloch-Pitts también utiliza diagramas con estados y transiciones, además de los conceptos de entrada y salida.
Formalmente, un autómata finito esuna Quíntupla (Q, Σ, q0, δ, F) donde:
Q: es un conjunto finito de estados;
Σ: es un alfabeto finito;
q0: es el estado inicial;
δ: es una función de transición;
F: es un conjunto de estados finales o de aceptación.

Representación como diagramas de estados

* Los autómatas finitos se pueden representar mediante grafos particulares, también llamados diagramas de estados finitos, de lasiguiente manera:
* Los estados Q se representan como vértices, etiquetados con su nombre en el interior.
* Una transición δ desde un estado a otro, dependiente de un símbolo del alfabeto, se representa mediante una arista dirigida que une a estos vértices, y que está etiquetada con dicho símbolo.
* El estado inicial q0 se caracteriza por tener una arista que llega a él, proveniente...