Autómata
Páginas: 10 (2358 palabras)
Publicado: 30 de julio de 2011
INTRODUCCIÓN
Un Autómata finito es similar a una máquina de estado finito sin embargo lo que caracteriza a una de la otra es que los autómatas finitos solo tienen dos estados, un estado interno y uno de rechazo. está formado por una quíntupla . A= Símbolos de entrada S= Estados internos T= un Subconjunto de S (Estado de Aceptación) q0= Estado inicial F= Función de próximo estado F= S x A-→ S. Los Autómatas finitos constituyen un modelo útil para muchos tipos importantes de hardware y software. Estos son algunos ejemplos: Software para el diseño y la verificación del comportamiento de circuitos digitales, el analizador léxico de un compilador típico, esto es la componente del compilador que descompone el texto inicial en unidades lógicas tales como identificadores, palabrasreservadas y signos de puntuación. Software para explorar grandes cuerpos de texto, como conjuntos de páginas web, o para descubrir las apariciones de ciertas palabras, frases u otros patrones. Software para comprobar la corrección de cualquier tipo de sistemas que tengan un número finito de estados diferentes.
La ventaja de tener solo un número finito de estados es que el sistema se puedeimplementar con un volumen fijo de recursos. Por ejemplo podría hacerse una implementación de hardware con un circuito, o mediante un programa sencillo que decida en función de un conjunto limitados de datos.
AUTÓMATAS
AUTÓMATA FINITO
Un autómata finito (AF) o máquina de estado finito es un modelo matemático 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 finalmentedetenerse en 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.
Historia
El origen de los autómatas finitos probablemente se remonta a su uso implícito en máquinas electromecánicas, desde principios del siglo XX. Ya en1907, 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, que poseen una memoria primitiva similar, en que la activación de un estado también depende del estado anterior, así como del símbolo opalabra 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 de secuencia; se establecen muchas de sus propiedades básicas, incluyendo su interpretación como lenguajes regulares y suequivalencia 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 los sistemas de sobreescritura. Finalmente, con el desarrollo del sistema operativo Unix en la década de 1970, los autómatas finitosencuentran 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 comienzan a utilizar en sistemas dinámicos.
El modelo neuronal de McCulloch-Pitts también utiliza diagramas con estados y...
Un Autómata finito es similar a una máquina de estado finito sin embargo lo que caracteriza a una de la otra es que los autómatas finitos solo tienen dos estados, un estado interno y uno de rechazo. está formado por una quíntupla . A= Símbolos de entrada S= Estados internos T= un Subconjunto de S (Estado de Aceptación) q0= Estado inicial F= Función de próximo estado F= S x A-→ S. Los Autómatas finitos constituyen un modelo útil para muchos tipos importantes de hardware y software. Estos son algunos ejemplos: Software para el diseño y la verificación del comportamiento de circuitos digitales, el analizador léxico de un compilador típico, esto es la componente del compilador que descompone el texto inicial en unidades lógicas tales como identificadores, palabrasreservadas y signos de puntuación. Software para explorar grandes cuerpos de texto, como conjuntos de páginas web, o para descubrir las apariciones de ciertas palabras, frases u otros patrones. Software para comprobar la corrección de cualquier tipo de sistemas que tengan un número finito de estados diferentes.
La ventaja de tener solo un número finito de estados es que el sistema se puedeimplementar con un volumen fijo de recursos. Por ejemplo podría hacerse una implementación de hardware con un circuito, o mediante un programa sencillo que decida en función de un conjunto limitados de datos.
AUTÓMATAS
AUTÓMATA FINITO
Un autómata finito (AF) o máquina de estado finito es un modelo matemático 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 finalmentedetenerse en 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.
Historia
El origen de los autómatas finitos probablemente se remonta a su uso implícito en máquinas electromecánicas, desde principios del siglo XX. Ya en1907, 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, que poseen una memoria primitiva similar, en que la activación de un estado también depende del estado anterior, así como del símbolo opalabra 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 de secuencia; se establecen muchas de sus propiedades básicas, incluyendo su interpretación como lenguajes regulares y suequivalencia 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 los sistemas de sobreescritura. Finalmente, con el desarrollo del sistema operativo Unix en la década de 1970, los autómatas finitosencuentran 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 comienzan a utilizar en sistemas dinámicos.
El modelo neuronal de McCulloch-Pitts también utiliza diagramas con estados y...
Leer documento completo
Regístrate para leer el documento completo.